doi:10.1093/comjnl/bxl007 Improved Algorithms for the K-Maximum Subarray Problem

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ðminfK + n log2n ‚ n ffiffiffiffi p KgÞ 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 twodimensional case, we introduce two techniques that establish O(n 3) and subcubic time