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 a1, a2,… ,...

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 a1, a2,… , an,
the algorithm computes the maximum sum ∑k(top) i=j(bottom) a_i
where 1 ≤ j ≤ k ≤ n.

b) Let M(k) be the maximum of the sums of consecutive
terms of the sequence ending at ak. That is, M(k) =
max1≤j≤k
∑k
i=j ai
. Explain why the recurrence relation
M(k) = max(M(k − 1) + ak, ak) 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.