On locating disjoint segments with maximum sum of densities
Journal
Algorithmica (New York)
Journal Volume
54
Journal Issue
1
Pages
107 - 117
Date Issued
2009
Author(s)
Liu, Hsiao-Fei
Abstract
Given a sequence A of n real numbers and two positive integers l and k, where ≤ nl, 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. © 2007 Springer Science+Business Media, LLC.
Type
journal article