Chung, Kai-MinKai-MinChungHSUEH-I LU2020-05-042020-05-042003https://www.scopus.com/inward/record.uri?eid=2-s2.0-0142152742&doi=10.1007%2f978-3-540-39658-1_15&partnerID=40&md5=d605d49b13a42c01940c55e69533f4bbWe address a fundamental string problem arising from analysis of biomolecular sequences. The input consists of two integers L and U and a sequence S of n number pairs (ai, wi) with Wi > 0. Let segment S(i,j) of S be the consecutive subsequence of S starting index i to index j. The density of S(i, j) is d(i,j) = (ai + a i+1 + ... + aj)/(wi + Wi+1 + ... + Wj). The maximum-density segment problem is to find a maximum-density segment over all segments of S with L ≤ wi+wi+1+ ...+wj ≤ U. The best previously known algorithm for the problem, due to Goldwasser, Kao, and Lu, runs in O(n log(U-L+1)) time. In the present paper, we solve the problem in O(n) time. Our approach bypasses the complicated right-skew decomposition, introduced by Lin, Jiang, and Chao. As a result, our algorithm has the capability to process the input sequence in an online manner, which is an important feature for dealing with genome-scale sequences. Moreover, for an input sequence S representable in O(k) space, we also show how to exploit the sparsity of S and solve the maximum-density segment problem for S in O(k) time. © Springer-Verlag 2003.Algorithms; Biomolecular sequences; Important features; Input sequence; Maximum-density segment; Optimal algorithm; Problem solvingconference paper10.1007/978-3-540-39658-1_152-s2.0-0142152742https://doi.org/10.1007/978-3-540-39658-1_15