Improved algorithms for the \(k\) maximum-sums problems (Q2508973)

Given a sequence of n real numbers and an integer \(k\), \(1\leq k\leq n(n-1)/2\), the \(k\) maximum-sum segments problem is to locate the \(k\) segments whose sums are the \(k\) largest among all possible segment sums. Recently, \textit{F. Bengtsson} and \textit{J. Chen} [Lect. Notes Comput. Sci. 3341, 137--148 (2004; Zbl 1100.68643), Algorithmica 46, No. 1, 27--41 (2006; Zbl 1100.68124)] gave an \(O(\min{k+nlog^2n,n\sqrt{k}})\)-time algorithm for this problem. S. E. Bae and T. Takaoka later proposed a more efficient algorithm for small \(k\). In this paper, we propose an \(O(n+k\log(\min\{n,k\}))\)-time algorithm for the same problem, which is superior to both of them when \(k\) is \(o(n \log n)\). We also give the first optimal algorithm for delivering the \(k\) maximum-sum segments in non-decreasing order if \(k\leq n\). Then we develop an \(O(n^{2d-1}+k\log(\min\{n,k\}))\)-time algorithm for the \(d\)-dimensional version of the problem, where \(d>1\) and each dimension, without loss of generality, is of the same size \(n\). This improves the best previously known \(O(n^{2d-1}C)\)-time algorithm, also by Bengtsson and Chen, where \(C=\min \{k+n\log^2n, n\sqrt{k}\}\). It should be pointed out that, given a two-dimensional array of size \(m\times n\), our algorithm for finding the \(k\) maximum-sum subarrays is the first one achieving cubic time provided that \(k\) is \(O(m^2n/\log n)\).