Question $1$: Dynamic Programming $$ Maximum Value Contiguous Subsequence $(20$ points$)$

Given a sequence of n integers A$(1),....,$ A$($n$),$ determine a contiguous subsequence A$($i$),...,$ A$($j$)$ for which the sum of

elements in the subsequence is maximized. For example, for number sequence $\{-2,11,-4,13,-5,2\},$ the maximum

value contiguous subsequence is $\{11,-4,13\},$ with maximum value $20.$ Obviously, if all numbers in the sequence are

positive, the entire sequence is the answer; if all numbers in the sequence are negative, an empty string is the answer.

a$.$ First give a simple and correct O$($n$3)$ algorithm to solve it$.$

b$.$ Then design a more efficient algorithm using dynamic programming. Hint: Let M$[$j$]$ denote the maximum

sum over the subsequence A$(1),$ A$(2),...$A$($j$).$

c$.$ What is the time complexity of your dynamic programming algorithm?

d$.$ Use your dynamic programming algorithm to solve the example: $\{-2,11,-4,13,-5,2\}.$