https://scholars.lib.ntu.edu.tw/handle/123456789/348869
Title: | Optimal algorithms for the average-constrained maximum-sum segment problem | Authors: | Cheng, C.-H. Liu, H.-F. KUN-MAO CHAO |
Keywords: | Algorithms; Association rules; Average; Maximum-sum segment | Issue Date: | 2009 | Journal Volume: | 109 | Journal Issue: | 3 | Start page/Pages: | 171-174 | Source: | Information Processing Letters | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-57349115452&doi=10.1016%2fj.ipl.2008.09.024&partnerID=40&md5=635de9109c314a3c2281b4ac49ab0bcb http://scholars.lib.ntu.edu.tw/handle/123456789/348869 |
ISSN: | 00200190 | DOI: | 10.1016/j.ipl.2008.09.024 | SDG/Keyword: | Associative processing; Number theory; Average; Lower bounds; Maximum-sum segment; Optimal algorithms; Real numbers; Time algorithms; Time complexities; Upper bounds; Control theory |
Appears in Collections: | 生醫電子與資訊學研究所 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.