Computing the k maximum subarrays fast
2004 (English)Report (Other academic)
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
IdentifiersURN: urn:nbn:se:ltu:diva-25205Local ID: e2ef04f0-ece6-11db-bc0c-000ea68e967bOAI: oai:DiVA.org:ltu-25205DiVA: diva2:998257
Godkänd; 2004; 20070417 (ysko)2016-09-292016-09-29Bibliographically approved