A Linear Time Algorithm for the k Maximal Sums Problem

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

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²· 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.ppt (435 Kb)

BIBT_EX entry

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