I will give thumbs up for the answer. I have provided all the documentation needed below. Please let me know if something isn't clear.

Dynamic programming: LIS (10 points)

We looked at the Longest Increasing Subsequence (LIS) problem in the textbook (section 3.6). Using the pseudocode found on page 110, write a program called LIS.java or lis.py that implements the FastLIS method. As usual, also implement a main method or section that:

1. Initializes an array A with the values 0, 60, 10, 70, 20, 80, 30, 90, 50, 100, 60, 110, 70, 120, 80, 90. The 0 at the beginning is not part of the sequence but is put there to get the method working.
2. Calls the LIS method, which takes A as a parameter and returns the length of the longest increasing subsequence. In this case, the length is 8.
3. Prints the length with a suitable message.

Longest Increasing Subsequence (LIS) problem in the textbook (section 3.6)

3.6 Longest Increasing Subsequence Another problem we considered in the previous chapter was computing the length of the longest increasing subsequence of a given array A[1..n] of numbers. We developed two different recursive backtracking algorithms for this problem. Both algorithms run in O(2") time in the worst case; both algorithms can be sped up significantly via dynamic programming. First Recurrence: Is This Next? Our first backtracking algorithm evaluated the function LISbigger(i, j), which we defined as the length of the longest increasing subsequence of A[j.. n) in which every element is larger than A[i]. We derived the following recurrence for this function: 0 if j>n if A[i]> A[j] LISbigger(i, j)= LISbigger(i, j +1) LISbigger(i, j +1) U (1+LISbigger(j, j +1)S max otherwise To solve the original problem, we can add a sentinel value A[0] = =-OO to the array and compute LISbigger(0,1). Each recursive subproblem is identified by two indices i and j, so there are only O(na) distinct recursive subproblems to consider. We can memoize the re- sults of these subproblems into a two-dimensional array LISbigger[o..n, 1..n].12 Moreover, each subproblem can be solved in O(1) time, not counting recursive calls, so we should expect the final dynamic programming algorithm to run in O(na) time. The order in which the memoized recursive algorithm fills this array is not immediately clear; all we can tell from the recurrence is that each entry LISbigger[i, j] is filled in after the entries LISbigger[i,j+1] and LISbigger[j,j+1] in the next column, as indicated on the left in Figure 3.4. Fortunately, this partial information is enough to give us a valid evaluation order. If we fill the table one column at a time, from right to left, then whenever we reach an entry in the table, the entries it depends on are already available. This may not be the order that the recursive algorithm would use, but it works, so we'll go with it. The right figure in Figure 3.4 illustrates this evaluation order, with a double arrow indicating the outer loop and single arrows indicating the 12 In fact, we only need half of this array, because we always have i A[j] LISbigger[i,j] + skip else LISbigger[i,j] + max{keep, skip} return LISbigger[0,1]