Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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. , p. 7
Series
Research report / Luleå University of Technology, ISSN 1402-1528 ; 2004:07
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-25205Local ID: e2ef04f0-ece6-11db-bc0c-000ea68e967bOAI: oai:DiVA.org:ltu-25205DiVA: diva2:998257
Note
Godkänd; 2004; 20070417 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

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

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 46 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

urn-nbn

Altmetric score

urn-nbn
Total: 32 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf