Efficient Algorithms for the Sum Selection Problem and K Maximum Sums Problem

Abstract

Given a sequence of n real numbers A = a ₁, a ₂,..., a _n and a positive integer k, the Sum Selection Problem is to find the segment A(i,j) = a _i , a _i + 1,..., a _j such that the rank of the sum s(i, j) = ∑ _t = i ^j a _t is k over all $\frac{n(n-1)}{2}$ segments. We present a deterministic algorithm for this problem that runs in O(n logn) time. The previously best known randomized algorithm for this problem runs in expected O(n logn) 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(n logn + k) time. The previously best known randomized and deterministic algorithms for the k Maximum Sums Problem run respectively in expected O(n logn + k) and O(n log² n + k) time in the worst case.

Research supported in part by the National Science Council under the Grants No. NSC-94-2213-E-001-004, NSC-95-2221-E-001-016-MY3, and NSC 94-2752-E-002-005-PAE, and by the Taiwan Information Security Center (TWISC), National Science Council under the Grant No. NSC94-3114-P-001-001-Y.