Problem 2. Given a sequence of n real numbers A = [a1, A2, A3, ..., an], the goal is to find a contiguous subsequence ai, ai+1,...,a; for which the sum of elements in the subsequence (i.e., s = {k=i ak) is maximized. (i) Give an efficient Dynamic Programming algorithm to find the desired. (ii) Give the best Divide-and-Conquer algorithm you can for finding the desired subse- quence. Compare the performance of your algorithm with the Dynamic Programming algorithm discussed in the PSO session