Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint

We study several fundamental problems arising from biological sequence analysis. Given a sequence of real numbers, we present two linear-time algorithms, one for locating the "longest" sum-constrained segment, and the other for locating the "shortest" sum-constrained segment. These two algorithms are based on the same framework and run in an online manner, hence they are capable of handling data stream inputs. Our algorithms also yield online linear-time solutions for finding the longest and shortest average-constrained segments by a simple reduction. © 2005 Elsevier B.V. All rights reserved.