1. Linear time computation of the maximal linear and circular sums of multiple independent insertions into a sequence.
- Author
-
Corrêa, Ricardo C. and Farias, Pablo M.S.
- Subjects
- *
LINEAR time invariant systems , *ALGORITHMS , *REAL numbers , *WIRELESS mesh networks , *WIRELESS communications - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF