Change search
ReferencesLink to record
Permanent link

Direct link
A note on ranking k maximum sums
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
2005 (English)Report (Other academic)
Abstract [en]

In this paper, we design a fast algorithm for ranking the k maximum sum subsequences. Given a sequence of real numbers and an integer parameter k, the problem is to compute k subsequences of consecutive elements with the sums of their elements being the largest, second largest, ..., and the k:th largest among all possible range sums. For any value of k, 1 <= k <= n(n+1)/2, our algorithm takes O(n + k log n) time in the worst case to rank all such subsequences. Our algorithm is optimal for k <= n.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2005. , 9 p.
Research report / Luleå University of Technology, ISSN 1402-1528 ; 2005:08
Research subject
Dependable Communication and Computation Systems
URN: urn:nbn:se:ltu:diva-23826Local ID: 894036c0-b2a0-11db-bf9d-000ea68e967bOAI: diva2:996876
Godkänd; 2005; 20070202 (ysko)Available from: 2016-09-29 Created: 2016-09-29Bibliographically approved

Open Access in DiVA

fulltext(176 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 176 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
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