# A Linear Time Algorithm for the *k* Maximal Sums Problem

In * Proc. 32nd International Symposium on Mathematical Foundations of Computer Science*, volume 4708 of * Lecture Notes in Computer Science*, pages 442-453. Springer Verlag, Berlin, 2007.

## Abstract

Finding the sub-vector with the largest sum in a sequence of *n*
numbers is known as the maximum sum problem. Finding the *k*
sub-vectors with the largest sums is a natural extension of this,
and is known as the *k* maximal sums problem. In this paper we
design an optimal *O*(*n*+*k*) time algorithm for the *k* maximal sums
problem. We use this algorithm to obtain algorithms solving the
two-dimensional *k* maximal sums problem in *O*(*m*^{2}· *n* + *k*)
time, where the input is an *m* x *n* matrix with *m*≤ *n*. We
generalize this algorithm to solve the *d*-dimensional problem
in *O*(*n*^{2d-1} + *k*) time. The space usage of all the algorithms can
be reduced to *O*(*n*^{d-1}+*k*). This leads to the first algorithm for
the *k* maximal sums problem in one dimension using *O*(*n*+*k*) time
and *O*(*k*) space.

**Copyright notice**
© Springer-Verlag Berlin Heidelberg 2007. All rights reserved.

**Online version**

mfcs07sum.pdf (157 Kb)

**DOI**

10.1007/978-3-540-74456-6_40

**Slides**
mfcs07sum.pdf (599 Kb), mfcs07sum.ppt (435 Kb)

**BIBT**_{E}X entry

@incollection{mfcs07sum,
author = "Gerth St{\o}lting Brodal and Allan Gr{\o}nlund J{\o}rgensen",
booktitle = "Proc. 32nd International Symposium on Mathematical Foundations of Computer Science",
doi = "10.1007/978-3-540-74456-6_40",
isbn = "978-3-540-74455-9",
pages = "442-453",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "A Linear Time Algorithm for the $k$ Maximal Sums Problem",
volume = "4708",
year = "2007"
}

l>