Efficient Algorithms for the Maximum Convex Sum Problem

This research is designed to develop and investigate newly defined problems: the Maximum Convex Sum (MCS), and its generalisation, the K-Maximum Convex Sum (K-MCS), in a two-dimensional (2D) array based on dynamic programming. The study centres on the concept of finding the most useful informative array portion as defined by different parameters involved in data, which is generically expressed in this thesis as the Maximum Sum Problem (MSP). This concept originates in the Maximum Sub-Array (MSA) problem, which relies on rectangular regions to find the informative array portion. From the above it follows that MSA and MCS belong to MSP. This research takes a new stand in using an alternative shape in the MSP context, which is the convex shape. Since 1977, there has been substantial research in the development of the Maximum Sub-Array (MSA) problem to find informative sub-array portions, running in the best possible time complexity. Conventionally the research norm has been to use the rectangular shape in the MSA framework without any investigation into an alternative shape for the MSP. Theoretically there are shapes that can improve the MSP outcome and their utility in applications; research has rarely discussed this. To advocate the use of a different shape in the MSP context requires rigorous investigation and also the creation of a platform to launch a new exploratory research area. This can then be developed further by considering the implications and practicality of the new approach. This thesis strives to open up a new research frontier based on using the convex shape in the MSP context. This research defines the new MCS problem in 2D; develops and evaluates algorithms that serve the MCS problem running in the best possible time complexity; incorporates techniques to advance the MCS algorithms; generalises the MCS problem to cover the K-Disjoint Maximum Convex Sums (K-DMCS) problem and the K-Overlapping Maximum Convex Sums (K-OMCS) problem; and eventually implements the MCS algorithmic framework using real data in an ecology application. Thus, this thesis provides a theoretical and practical framework that scientifically contributes to addressing some of the research gaps in the MSP and the new research path: the MCS problem. The MCS and K-MCS algorithmic models depart from using the rectangular shape as in MSA, and retain a time complexity that is within the best known time complexities of the MSA algorithms. Future in-depth studies on the Maximum Convex Sum (MCS) problem can advance the algorithms developed in this thesis and their time complexity