Linear time computation of the maximal sums of insertions into all positions of a sequence

Let the maximal sum of a sequence A be the greatest sum of a contiguous and possibly empty subsequence S of A. Given sequences A and X of n and n + 1 numbers respectively, let A ( i ) be the sequence which results from the insertion of element X [ i ] between elements A [ i − 1 ] and A [ i ] of A. It is known that computing the maximal sum of A ( i ) can be done in linear time. We show that the simultaneous computation of the maximal sums of A ( 0 ) , A ( 1 ) , … , A ( n ) can also be done in linear time. Such an algorithm has applications to buffer minimization in radio networks.