Fast Algorithms for the Generalized Maximum Subarray Problem.

Sung Eun Bae, Ph.D Student

Dept of CSSE, University of Canterbury

Wed Sep 05 10:00:00 NZST 2007 in Room 031, MSCS

Abstract

The maximum subarray problem (MSP) involves selection of a segment of consecutive array elements that has the largest possible sum. A solution to this problem is expected to contribute to genomic sequence analysis, data mining and computer vision.

We generalize the problem and we are interested in K segments of the largest sum in sorted order. There are two cases, where K segments overlap or they are disjoint. Each case requires significantly different techniques to efficiently compute.

A quest for faster algorithms for two problems resulted in O(n+Klog K) time solutions. Particularly, for the overlapping case, this is a significant improvement from the O(Kn) time algorithm achieved at the earlier stage of this research.

Techniques for extending these new algorithms to 2D enabled to hit O(n^3) time for small, but practically large enough K. Roughly speaking, we can find K maximum subarrays spending the same amount of time for just one maximum subarray.

Finally, we review a mesh-type parallel algorithm for the MSP in an attempt to overcome near-cubic time complexity of sequential algorithms. The new solution is more practical than currently known parallel algorithms. It is less hardware-resource demanding, chip-implementable, scalable and supports data loading on-the-fly.