Randomized algorithm for the sum selection problem

Let A be a sequence of n real numbers a1,a2,…,an. We consider the Sum Selection Problem as that of finding the segment A(i∗,j∗) such that the rank of over all possible feasible segments is k, where a feasible segment A(i,j)=ai,ai+1,…,aj is a consecutive subsequence of A, and its width j−i+1 satisfies ℓ≤j−i+1≤u for some given integers ℓ and u, and ℓ≤u. It is a generalization of two well-known problems: the Selection Problem in computer science for which ℓ=u=1, and the Maximum Sum Segment Problem in bioinformatics for which the rank k is the total number of possible feasible segments. We will give a randomized algorithm for the Sum Selection Problem that runs in expected O(nlog(u−ℓ)) time. It matches the optimal O(n) time randomized algorithm for the Selection Problem. We can also solve the k Maximum Sums Problem, to enumerate the k largest sums, in expected O(nlog(u−ℓ)+k) time. The previously best known result was an algorithm that solves this problem for the case when ℓ=1, u=n and runs in O(nlog2n+k) time in the worst case.