A Linear Time Algorithm for the k Maximal Sums Problem

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 × n matrix with m ≤ n. We generalize this algorithm to solve the d -dimensional problem in O ( n 2 d − 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.

Authors

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

Keywords

No keywords are indexed for this paper.