Selecting Sums in Arrays

Gerth Stølting Brodal and Allan Grønlund Jørgensen

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.

Abstract

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

10.1007/978-3-540-92182-0_12

Links

BIBTEX entry

@incollection{isaac08,
  author = "Gerth St{\o}lting Brodal and Allan Gr{\o}nlund J{\o}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"
}