Improved algorithms for the \(k\) maximum-sums problems

DOI10.1016/j.tcs.2006.06.007zbMath1155.68604MaRDI QIDQ2508973

Chih-Huai Cheng, Kuan-Yu Chen, Kun-Mao Chao, Wen-Chin Tien

Publication date: 20 October 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.06.007

zbMATH Keywords

sequence analysis; maximum-sum subarray; maximum-sum subsequence

Mathematics Subject Classification ID

68W40: Analysis of algorithms

Related Items

Randomized algorithm for the sum selection problem, Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence, Optimal algorithms for the average-constrained maximum-sum segment problem, Robust optimization in the presence of uncertainty: a generic approach, Efficient algorithms for the sum selection problem and \(k\) maximum sums problem

Uses Software

• MAVG
• SEGID

Cites Work

• Unnamed Item
• Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint
• Pattern analysis. Lectures in pattern theory. Vol. II
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• An Optimal Algorithm for Maximum-Sum Segment and Its Application in Bioinformatics
• Algorithms and Computation
• Algorithms and Computation
• Computing and Combinatorics
• Algorithms and Computation