Randomized Algorithm for the Sum Selection 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 $s(i, j) = \sum_{t = i}^{j}{a_{t}}$ is k over all ${n(n-1)} \over {2}$ segments. We will give a randomized algorithm for this problem that runs in expected O(n log n) time. Applying this algorithm we can obtain an algorithm for the kMaximum Sums Problem, i.e., the problem of enumerating the k largest sum segments, that runs in expected O(n log n + k) time. The previously best known algorithm for the kMaximum Sums Problem runs in O(n log2n + k) time in the worst case.