Open AccessOn Locating Disjoint Segments with Maximum Sum of Densities
Author(s) -
Hsiao-Fei Liu,
KunMao Chao
Publication year - 2006
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
DOI - 10.1007/11940128_31
Subject(s) - disjoint sets , combinatorics , sequence (biology) , mathematics , running time , discrete mathematics , algorithm , chemistry , biochemistry
Given a sequence A of n real numbers and two positive integers l and k, where $k \leq \frac{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 [1], runs in O(nl+k2l2) time. In this paper, we give an O(n+k2llogl)-time algorithm.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom