Efficient algorithms for the sum selection problem and k maximum sums problem

Given a sequence of n real numbers A=a1,a2,…,an and a positive integer k, the Sum Selection Problem is to find the segment A(i∗,j∗)=ai∗,ai∗+1,…,aj∗ such that the rank of the sum is k over all segments. We present a deterministic algorithm for this problem that runs in O(nlogn) time. The previously best known result for this problem is a randomized algorithm that runs in expected O(nlogn) time. Applying this algorithm we can obtain a deterministic algorithm for the k Maximum Sums Problem, i.e., the problem of enumerating the k largest sum segments, that runs in O(nlogn+k) time. The previously best known randomized and deterministic algorithms for the k Maximum Sums Problem run respectively in expected O(nlogn+k) time and in worst case O(nlog2n+k) time.