Optimal algorithms for the average-constrained maximum-sum segment problem
Resource
Information Processing Letters 109 (3): 171-174
Journal
Information Processing Letters
Journal Volume
109
Journal Issue
3
Pages
171-174
Date Issued
2009
Author(s)
Abstract
Given a real number sequence A = (a1, a2, ..., an), an average lower bound L, and an average upper bound U, the Average-Constrained Maximum-Sum Segment problem is to locate a segment A (i, j) = (ai, ai + 1, ..., aj) that maximizes ∑i ≤ k ≤ j ak subject to L ≤ frac((∑i ≤ k ≤ j ak), (j - i + 1)) ≤ U. In this paper, we give an O (n)-time algorithm for the case where the average upper bound is ineffective, i.e., U = ∞. On the other hand, we prove that the time complexity of the problem with an effective average upper bound is Ω (n log n) even if the average lower bound is ineffective, i.e., L = - ∞. © 2008 Elsevier B.V. All rights reserved.
Subjects
Algorithms; Association rules; Average; Maximum-sum segment
Other Subjects
Associative processing; Number theory; Average; Lower bounds; Maximum-sum segment; Optimal algorithms; Real numbers; Time algorithms; Time complexities; Upper bounds; Control theory
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
22.pdf
Size
162.45 KB
Format
Adobe PDF
Checksum
(MD5):d4de59444a63604340d9193ce4e55346