Write a dynamic programming algorithm to solve the longest increasing subsequence (LIS) problem. You are given an array A of n integers. An increasing subsequence is a sequence of k indices 0 i1 < i2 < . . . < ik (n 1) such that A[i1] < A[i2] < . . . < A[ik]. Thus, given an array A, you are to compute an increasing subsequence i1, . . . , ik whose length k is the longest possible. Example: A = [1, 5, 2, 3, 8]. The longest increasing subsequence has length 4 with corresponding indices i = [0, 2, 3, 4]. Lets define the function LIS(A, j, M) to be length of the LIS for the first j elements of the array (A[0], . . . , A[j 1]), where j ranges from 0 to n and all elements of this subsequence are less than M.

a) For A = [1, 5, 2, 3, 8], write down the values of LIS(A, 4, 3) and LIS(A, 5, ).

b) Write down the base case for LIS(A, 0, M).

c) Write down the recurrence for LIS(A, j, M) for any 1 j n.

d) Describe a scheme to memoize the recurrence LIS above.