Efficient Algorithms for the Maximum Convex Sum Problem

The work of this thesis covers the Maximum Subarray Problem (MSP) from a new perspective. Research done previously and current methods of finding MSP include using the rectangular shape for finding the maximum sum or gain. The rectangular shape region used previously is not flexible enough to cover various data distributions. This research suggested using the convex shape, which is expected to have optimised and efficient results. The steps to build towards using the proposed convex shape in the context of MSP are as follows: studying the available research in-depth to extract the potential guidelines for this thesis research; implementing an appropriate convex shape algorithm; generalising the main algorithm (based on dynamic programming) to find the second maximum sum, the third maximum sum and up to Kth maximum sum; and finally conducting experiments to evaluate the outcomes of the algorithms in terms of the maximum gain, time complexity, and the running time. In this research, the following findings were achieved: one of the achievements is presenting an efficient algorithm, which determines the boundaries of the convex shape while having the same time complexity as other existing algorithms (the prefix sum was used to speed up the convex shape algorithm in finding the maximum sum). Besides the first achievement, the algorithm was generalized to find up to the Kth maximum sum. Finding the Kth maximum convex sum was shown to be useful in many applications, one of these (based on a study with the cooperation of Christchurch Hospital in New Zealand) is accurately and efficiently locating brain tumours. Beside this application, the research findings present new approaches to applying MSP algorithms in real life applications, such as data mining, computer vision, astronomy, economics, chemistry, and medicine