Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Computing the k maximum subarrays fast
Luleå tekniska universitet, Institutionen för system- och rymdteknik, Datavetenskap.
2004 (Engelska)Rapport (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Luleå: Luleå tekniska universitet, 2004. , s. 7
Serie
Forskningsrapport / Luleå tekniska universitet, ISSN 1402-1528 ; 2004:07
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
URN: urn:nbn:se:ltu:diva-25205Lokalt ID: e2ef04f0-ece6-11db-bc0c-000ea68e967bOAI: oai:DiVA.org:ltu-25205DiVA, id: diva2:998257
Anmärkning
Godkänd; 2004; 20070417 (ysko)Tillgänglig från: 2016-09-29 Skapad: 2016-09-29 Senast uppdaterad: 2018-01-10Bibliografiskt granskad

Open Access i DiVA

fulltext(147 kB)123 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 147 kBChecksumma SHA-512
d62a7a11637981a027f0ac88e894dd81f588d7fa199f6b060585758aa79132283c159ec73318db01f9a22241c6faedea99a7b6aef85ec4f594aa2cb12e09d622
Typ fulltextMimetyp application/pdf

Personposter BETA

Bengtsson, FredrikChen, Jingsen

Sök vidare i DiVA

Av författaren/redaktören
Bengtsson, FredrikChen, Jingsen
Av organisationen
Datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 123 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 63 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf