# Selecting Sums in Arrays

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**

**BIBT**_{E}X 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"
}