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 linea
In this exercise we will develop a dynamic
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
. 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.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 4 images
