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.