Aarhus University Seal

A Linear Time Algorithm for the k Maximal Sums Problem

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
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 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.
Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2007 : 32nd International Symposium, MFCS 2007 Ceský Krumlov, Czech Republic, August 26-31, 2007 Proceedings
EditorsLudek Kucera, Antonin Kucera
Number of pages12
Publication year2007
ISBN (print)978-3-540-74455-9
Publication statusPublished - 2007
Event32nd International Symposium on Mathematical Foundations of Computer Science - Cesky Krumlov, Czech Republic
Duration: 26 Aug 200731 Aug 2007
Conference number: 32


Conference32nd International Symposium on Mathematical Foundations of Computer Science
LandCzech Republic
ByCesky Krumlov
SeriesLecture Notes in Computer Science

    Research areas

  • maximum sum problem

See relations at Aarhus University Citationformats

ID: 5651233