Chapter 8.1, Problem 56E

In this exercise we will develop a dynamic programming algorithm for finding the maximum sum of consecutive terms of a sequence of real numbers. That is, given a sequence of real numbers $a_1,a_2,\mathrm{...},a_n$, the algorithm computes the maximum sum ${\displaystyle {\sum }_{i=1}^k{a}_i}$ , where $1\le j\le k\le n$.

a) Show that if all terms of the sequence are nonnegative, this problem is solved by taking the sum of all terms. Then, give an example where the maximum sum of consecutive terms is not the sum of all terms.

b) Let $M\left(k\right)$ be the maximum of the sums of consecutive terms of the sequence ending at $a_k$ . That is, $M\left(k\right)={\max }_{1\le j\le k}{\displaystyle {\sum }_{i=1}^k{a}_i}$ , Explain why the recurrence relation $M\left(k\right)=\max \left(M\left(k-1\right)+a_k,a_k\right)$holds for k = 2, ...,n.

c) Use part (b) to develop a dynamic programming algorithm for solving this problem.

d) Show each step your algorithm from part (c) uses to find the maximum sum of consecutive terms of the sequence 2, -3, 4, 1, -2, 3.

e) Show that the worst-case complexity in terms of the number of additions and comparisons of your algorithm from part (c) is linear.