Change search
ReferencesLink to record
Permanent link

Direct link
Computing the k maximum subarrays fast
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
2004 (English)Report (Other academic)
Abstract [en]

We study the problem of computing the k maximum sum subarrays. Given an array of real numbers and an integer, k, the problem involves finding the k largest values of the sum from i to j of the array, for any i and j. The problem for fixed k=1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. In this paper, we develop an algorithm requiring time proportional to n times square root of k for an array of length n. Moreover, for two-dimensional version of the problem, which computes the k largest sums over all rectangular subregions of an m times n array of real numbers, we show that it can be solved efficiently in the worst case as well.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2004. , 7 p.
Research report / Luleå University of Technology, ISSN 1402-1528 ; 2004:07
Research subject
Dependable Communication and Computation Systems
URN: urn:nbn:se:ltu:diva-25205Local ID: e2ef04f0-ece6-11db-bc0c-000ea68e967bOAI: diva2:998257
Godkänd; 2004; 20070417 (ysko)Available from: 2016-09-29 Created: 2016-09-29Bibliographically approved

Open Access in DiVA

fulltext(147 kB)3 downloads
File information
File name FULLTEXT01.pdfFile size 147 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Bengtsson, FredrikChen, Jingsen
By organisation
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 3 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link