Linear time computation of the maximal linear and circular sums of multiple independent insertions into a sequence.

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 ) time by means of Kadane's algorithm. Letting A ( x → p ) denote the sequence which results from inserting a real number x just after element A [ p − 1 ] , we show how the maximal sum of A ( x → p ) can be computed in O ( 1 ) worst-case time for any given x and p , provided that an O ( n ) time preprocessing step has already been executed on A . In particular, this implies that, given m pairs ( x 0 , p 0 ) , … , ( x m − 1 , p m − 1 ) , we can compute the maximal sums of sequences A ( x 0 → p 0 ) , … , A ( x m − 1 → p m − 1 ) optimally in O ( n + m ) time, improving on the straightforward and suboptimal strategy of applying Kadane's algorithm to each sequence A ( x i → p i ) , which takes a total of Θ ( n m ) time. We also show that the same time bound is attainable when circular subsequences of 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. [ABSTRACT FROM AUTHOR]