文摘
The maximal sum of a sequence A of n real numbers is the greatest sum of all elements of any linearly contiguous and possibly empty subsequence of A . It can be computed in O(n)O(n) time by means of Kadane's algorithm. Letting A(x→p)A(x→p) denote the sequence which results from inserting a real number x just after element A[p−1]A[p−1], we show how the maximal sum of A(x→p)A(x→p) can be computed in O(1)O(1)worst-case time for any given x and p , provided that an O(n)O(n) time preprocessing step has already been executed on A. In particular, this implies that, given m pairs (x0,p0),…,(xm−1,pm−1)(x0,p0),…,(xm−1,pm−1), we can compute the maximal sums of sequences A(x0→p0),…,A(xm−1→pm−1)A(x0→p0),…,A(xm−1→pm−1) optimally in O(n+m)O(n+m) time, improving on the straightforward and suboptimal strategy of applying Kadane's algorithm to each sequence A(xi→pi)A(xi→pi), which takes a total of Θ(nm)Θ(nm) time. We also show that the same time bound is attainable when circular subsequences of A(x→p)A(x→p) are taken into account. Our algorithms are easy to implement in practice, and they were motivated by a buffer minimization problem on wireless mesh networks.
