Improved algorithms for the K overlapping maximum convex sum problem

This paper presents efficient algorithms that improve the time complexity of the K-Overlapping Maximum Convex Sum Problem (K-OMCSP). Previous research has solved this problem by using the K-tuples approach in a time complexity of O(Kn3). In this paper, efficient algorithms based on dynamic programming are derived to improve the time complexity for the overlapping case. The algorithms find the first, second and third maximum convex sum, and up to the Kth maximum convex sum in the time complexity of O(n3+Kn2) applying a new method which we call Active Trace Overlapping-Shape (ATOS). In addition, efficient techniques have been developed for designing and implementing the derived algorithms. Moreover, experiments performed to compare the running time for the two methods. The experiments showed that the running time of ATOS was faster than the K-tuples.