In Proc. 19th Annual International Symposium on Algorithms and Computation, volume 5369 of Lecture Notes in Computer Science, pages 100-111. Springer Verlag, Berlin, 2008.
In an array of n numbers each of the \binom{n}{2}+n contiguous subarrays define a sum. In this paper we focus on algorithms for selecting and reporting maximal sums from an array of numbers. First, we consider the problem of reporting k subarrays inducing the k largest sums among all subarrays of length at least l and at most u. For this problem we design an optimal O(n+k) time algorithm. Secondly, we consider the problem of selecting a subarray storing the k'th largest sum. For this problem we prove a time bound of Θ(n · max{1,log (k/n)}) by describing an algorithm with this running time and by proving a matching lower bound. Finally, we combine the ideas and obtain an O(n· max{1,log (k/n)}) time algorithm that selects a subarray storing the k'th largest sum among all subarrays of length at least l and at most u.
Copyright notice© Springer-Verlag Berlin Heidelberg 2008. All rights reserved.
Online version
isaac08.pdf (176 Kb)
DOI
Links
BIBTEX entry
@incollection{isaac08,
author = "Gerth Stølting Brodal and Allan Grønlund Jørgensen",
booktitle = "Proc. 19th Annual International Symposium on Algorithms and Computation",
doi = "10.1007/978-3-540-92182-0_12",
isbn = "978-3-540-92181-3",
pages = "100-111",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "Selecting Sums in Arrays",
volume = "5369",
year = "2008"
}