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 k ≤ n/l, the problem is to locate k disjoint segments of A, each has length at least l, such that their sum of densities is maximized. The best previously known algorithm, due to Bergkvist and Damaschke, runs in O(nl + k~2l~2) time. In this paper, we give an O(n + k~2l log l)-time algorithm.