Let A be a sequence of n real numbers a(1), a(2),., a(n). We consider the sum SELECTION problem as that of finding the segment A(i*, j*) such that the rank of s(i*, j*) = Sigma(j*)(t=i) at over all possible feasible s...
详细信息
Let A be a sequence of n real numbers a(1), a(2),., a(n). We consider the sum SELECTION problem as that of finding the segment A(i*, j*) such that the rank of s(i*, j*) = Sigma(j*)(t=i) at over all possible feasible segments is k, where a feasible segment A (i, j) = a(i), a(i + 1),..., a(j) is a consecutive subsequence of A, and its width j - i + 1 satisfies l <= j - i + 1 <= u for some given integers t and it, and l <= u. It is a generalization of two well-known problems: the SELECTION problem in computer science for which e = it = 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(n log(u - l)) time. It matches the optimal O(n) time randomized algorithm for the SELECTION problem. We can also solve the K maximumsumS problem, to enumerate the k largest sums, in expected 0(n log(u - e) + k) time. The previously best known result was an algorithm that solves this problem for the case when f = 1, u = n and runs in O(n log(2) n + k) time in the worst case. (c) 2007 Elsevier B.V. All rights reserved.
暂无评论