On Locating Disjoint Segments with Maximum Sum of Densities

Given a sequence A of n real numbers and two positive integers l and k, where , we study the problem of locating k disjoint segments of A, each of length at least l, such that the sum of their densities is maximized. The best previously known algorithm, due to Bergkvist and Damaschke, runs in O(nl+k 2 l 2) time. In this paper, we propose an O(n+k 2 llog l)-time algorithm for it. We also give an optimal algorithm for a related problem raised by Lin et al. in 2003, where the goal is to locate k disjoint maximum-density segments in a given sequence.