Improved algorithms for the k maximum-sums problems
Journal
Theoretical Computer Science
Journal Volume
362
Journal Issue
1-3
Pages
162-170
Date Issued
2006
Author(s)
Abstract
Given a sequence of n real numbers and an integer k, 1 ≤ k ≤ frac(1, 2) n (n - 1), the k maximum-sum segments problem is to locate the k segments whose sums are the k largest among all possible segment sums. Recently, Bengtsson and Chen gave an O (min { k + n log2 n, n sqrt(k) })-time algorithm for this problem. Bae and Takaoka later proposed a more efficient algorithm for small k. In this paper, we propose an O (n + k log (min { n, k }))-time algorithm for the same problem, which is superior to both of them when k is o (n log n). We also give the first optimal algorithm for delivering the k maximum-sum segments in non-decreasing order if k ≤ n. Then we develop an O (n2 d - 1 + k log min { n, k })-time algorithm for the d-dimensional version of the problem, where d > 1 and each dimension, without loss of generality, is of the same size n. This improves the best previously known O (n2 d - 1 C)-time algorithm, also by Bengtsson and Chen, where C = min { k + n log2 n, n sqrt(k) }. It should be pointed out that, given a two-dimensional array of size m × n, our algorithm for finding the k maximum-sum subarrays is the first one achieving cubic time provided that k is O (m2 n / log n). © 2006 Elsevier B.V. All rights reserved.
Type
journal article