Please do in pseudocode.

Suppose you are given an array A,.. n of numbers, which may be positive, negative, or zero a) Let Sij denote All Al+AU]. Use dynamic programming to give an O(n2 algorithm to compute S for all 1siSjSn, and hence compute maxi S b) Let LLi] denotes max, s.J. Give a recurrence relation for LU) in terms of L[L . . . ,,-1]. Use your recurrence relation to give an O(n) time dynamic programming algorithm to compute L[1...n, and hence compute maxi Sj- c) Consider the naive recursive algorithms (without memorization, like Cut-Rod from class) . Will both running based on the recurrence relations to compute the answers to part(a) and part(b) times stay at O(n2) and O(n), respectively, only one of them (which one?), or none? d) Suggest appropriate modifications to your algorithm in part (b) to give an O(n) algorithm to compute maxij Ptj, where Pt-Ali] Ali +1]...Alj]. Assume that multiplication of any two numbers takes O(1) time Suppose you are given an array A,.. n of numbers, which may be positive, negative, or zero a) Let Sij denote All Al+AU]. Use dynamic programming to give an O(n2 algorithm to compute S for all 1siSjSn, and hence compute maxi S b) Let LLi] denotes max, s.J. Give a recurrence relation for LU) in terms of L[L . . . ,,-1]. Use your recurrence relation to give an O(n) time dynamic programming algorithm to compute L[1...n, and hence compute maxi Sj- c) Consider the naive recursive algorithms (without memorization, like Cut-Rod from class) . Will both running based on the recurrence relations to compute the answers to part(a) and part(b) times stay at O(n2) and O(n), respectively, only one of them (which one?), or none? d) Suggest appropriate modifications to your algorithm in part (b) to give an O(n) algorithm to compute maxij Ptj, where Pt-Ali] Ali +1]...Alj]. Assume that multiplication of any two numbers takes O(1) time