FöRFATTARE
Bengtsson, Fredrik; Chen, Jingsen

INSTITUTION
Systemteknik / Datalogi

SAMMANFATTNING
Given a sequence of length n, the problem studied in this report is to find a set of k disjoint subsequences of consecutive elements such that the total sum of all elements in the set is maximized. This problem arises in the analysis of DNA sequences. The previous best known algorithm requires time proportional to n times the inverse Ackermann function of (n,n), in the worst case. We present a linear-time algorithm, which is optimal, for this problem.

ISSN 1402-1528 / ISRN LTU-FR--07/03--SE / NR 2007:03