Algorithms for Problems on Maximum Density Segment

摘要

Let A be a sequence of n ordered pairs of real numbers (a_i,l_i) (i = 1,..., n) with l_i ＞ 0, and L and U be two positive real numbers with 0 ＜ L ≤ U. A segment, denoted by A[i,j],l ≤ i ≤ j ≤ n, of A is a consecutive subsequence of A between the indices i and j (i and j included). The length l[i,j], sum s[i,j] and density d[i,j] of a segment A[i,j] are l[i,j] = ∑_(t=i)~j l_t, s[i,j] = ∑_(t=i)~j a_t and d[i,j] =s[i,j]/l[i,j] respectively. A segment A[i,j] is feasible if L ≤ l[i,j] ≤ U. The length-constrained maximum density segment problem is to find a feasible segment of maximum density. We present a simple geometric algorithm for this problem for the uniform length case (U = 1 for all i), with time and space complexities in O(n) and O(U - L + 1) respectively. The k length-constrained maximum density segments problem is to find the k most dense length-constrained segments. For the uniform length case, we propose an algorithm for this problem with time complexity in O(min{nk,n lg(U - L + 1) + klg~2(U -L + 2),n(U-L + 1)}).