Cheng, C.-H.C.-H.ChengLiu, H.-F.H.-F.LiuKUN-MAO CHAO2018-09-102018-09-10200900200190https://www.scopus.com/inward/record.uri?eid=2-s2.0-57349115452&doi=10.1016%2fj.ipl.2008.09.024&partnerID=40&md5=635de9109c314a3c2281b4ac49ab0bcbhttp://scholars.lib.ntu.edu.tw/handle/123456789/348869Given 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.application/pdf166344 bytesapplication/pdfAlgorithms; Association rules; Average; Maximum-sum segmentAssociative processing; Number theory; Average; Lower bounds; Maximum-sum segment; Optimal algorithms; Real numbers; Time algorithms; Time complexities; Upper bounds; Control theoryjournal article10.1016/j.ipl.2008.09.0242-s2.0-57349115452