An efficient algorithm for the k maximum convex sums
Mohammed Thaher, Tadao Takaoka · Procedia Computer Science · 2010
Abstract This research presents efficient methods for computing the maximum sum in a subarray problem. Firstly, one of the presented methods uses an efficient algorithm that determines the boundaries of a convex shape to calculate the optimal gain. The time complexity of this algorithm is the same as that for other existing algorithms, such as Kadane’s algorithm. Furthermore, even though this algorithm involves complicated operations, the involved processes return the shape of the optimised solution. Secondly, a generalization of the derived efficient algorithm is presented in this paper. This algorithm finds the first maximum sum, second maximum sum and up to the k th maximum sum. Finding the kth maximum convex sum can be utilized in many applications, such as accurately and efficiently locating the spreading of cancer.