(10 points) Longest Increasing Subsequence. In the longest increasing subsequence problem, you are given as input an unsorted array A of length n, e.g A-5,2,10, 3,-1,6,8,9, 3 The goal is to find the longest strictly increasing subsequence of A. The subsequence need not be continguous. For example, the boxed numbers below indicate the longest increasing subsequence in our exaimple: To approach this problem, it is first helpful to define a "helper" function LIS(j) to compute the length of the longest increasing subsequence that ends at index j (and includes item Alj]). Here are examples or j 3 and j-i5: 5, 2105,2, 10,3, -1 Therefore LIS(3) should return 2, and LIS(5) should return 1. a) Write a recursive algorithm for LIS(j) (b) Translate this recursive algorithm into a recurrence. Define OPT(j) to be the length of the longest increasing subsequence ending at index j, and write a recurrence for OPT(j) in the array entry Mj] for all j (ending at any j) (c) Use this recurrence to write an iterative algorithm to compute the value of OPT(j) and store it (d) Use the computed optimal values to find the value of the overall longest increasing subsequence (10 points) Longest Increasing Subsequence. In the longest increasing subsequence problem, you are given as input an unsorted array A of length n, e.g A-5,2,10, 3,-1,6,8,9, 3 The goal is to find the longest strictly increasing subsequence of A. The subsequence need not be continguous. For example, the boxed numbers below indicate the longest increasing subsequence in our exaimple: To approach this problem, it is first helpful to define a "helper" function LIS(j) to compute the length of the longest increasing subsequence that ends at index j (and includes item Alj]). Here are examples or j 3 and j-i5: 5, 2105,2, 10,3, -1 Therefore LIS(3) should return 2, and LIS(5) should return 1. a) Write a recursive algorithm for LIS(j) (b) Translate this recursive algorithm into a recurrence. Define OPT(j) to be the length of the longest increasing subsequence ending at index j, and write a recurrence for OPT(j) in the array entry Mj] for all j (ending at any j) (c) Use this recurrence to write an iterative algorithm to compute the value of OPT(j) and store it (d) Use the computed optimal values to find the value of the overall longest increasing subsequence