Question 3 (Maximum Sum Increasing Subsequence) Given an array of n positive integers, design an algorithm to find the sum of marimum sum subse- quence of the given array such that the integers in the subsequence are sorted in non-decreasing order. For example, if input is (1, 101, 2, 3, 100, 4, 5), then output should be 106 (1+2+3+ 100), if the input array is [3, 4, 5, 10), then output should be 22 (3+4+5+10) and if the input array is [10,5, 4, 3), then output should be 10. 1. (10 points) Describe a dynamic programming algorithm for solving the above problem. 2. (20 points) Formulate a recurrence relation that can be used to find the sum of the maximum sum increasing subsequence. (Hint: Formulate a recur- rence relation s that indicates the maximum sum increasing subsequence in the subarray A[1..i] such that the last element in the subsequence is 3. (12 points) Use your recurrence relation to develop a bottom-up iterative algorithm for the problem. Write down a pseudo-code for your algorithm. 4. (4 points) Establish the running time of your algorithm