Improved Algorithms for the K-Maximum Subarray Problem
Sung Eun Bae · The Computer Journal · 2005
The maximum subarray problem is to find the contiguous array elements having the largest possible sum. We extend this problem to find K maximum subarrays. For general K maximum subarrays where overlapping is allowed, Bengtsson and Chen presented O(min{K + n log²n, n√K}) time algorithm for one-dimensional case, which finds unsorted subarrays. Our algorithm finds K maximum subarrays in sorted order with improved complexity of O ((n + K) log K). For the two-dimensional case, we introduce two techniques that establish O(n³) and subcubic time.