Efficient Algorithms for the Maximum Convex Sum Problem

Mohammed Thaher (Msc Student)

Dept. of Computer Science and Software Engineering, University of Canterbury

Wed Mar 19 09:00:00 NZDT 2008 in Room 315, Erskine Building

Abstract

Previous studies in Maximum Subarray Problems used a rectangular shape region to find the maximum subarray for a particular problem. In the proposed research, a convex shape is suggested. The rectangular shape region used previously is not flexible enough to cover various data distribution; the convex shape is more likely to result in relatively optimised results. Also in the proposed research, the current algorithm by Takeshi Fukuda and Yasuhiko Morimoto is to be generalised to an algorithm that computes the maximum convex sum, second maximum, and up to k-th maximum.