Your objective is to design and implement a dynamic programming algorithm to determine all instances of the Longest Increasing Subsequence in some arbitrary sequence of integers. You are not to use the recursive solution that I provided on overheads. That algorithm runs in exponential time, blindly doing a depth first search for the length of the LIS and then returning just one instance of the LIS.

The algorithm you should use to determine the length of the LIS of some sequence S is the one I discussed in class on Thursday, September 17. This algorithm actually produces a vector, LISLengthEndingAt, of length N, where N is the size of the sequence. The value in LISLengthEndingAt[i] is the length of the LIS that includes S[i] as its last item. For example,
if S = {5, 1, 3, -2, 2, 6, 4, -1},
then LISLengthEndingAt = {1, 1, 2, 1, 2, 3, 3, 2}
The length of the LIS is 3, the largest number in this vector, and there are six LIS's
{-2, 2, 4}, {1, 2, 4}, {1, 3, 4}, {-2, 2, 6}, {1, 2, 6}, {1, 3, 6}

Here is an algorithm (not quite legitimate C++ or Java) to fill in LISLengthEndingAt.

void fillInLISLengthEndingAt(vector<int> s, vector<int> &lisLengthEndingAt) {
    for (int i = 0; i<s.length; i++) {
        lisLengthEndingAt[i] = 1;
        for (int j=i-1; j>=0; j--)
            if (s[i]>s[j]) lisLengthEndingAt[i] = max(lisLengthEndingAt[i],lisLengthEndingAt[j]+1);
    }
}

This is clearly an O(N²) algorithm, but it just computes the lengths. You must now compute and print all the LIS's. In a separate assignment I will ask you to analyze your algorithm for doing this print phase.

To make it easy for you (and me) to test your solution, your program must request and input the value of N, the sequence length. This can be done through prompted console input, or via a GUI. Your program must then generate and output a sequence of random integers (keep these between -15 and +16 like in programming assignment#1), the length of the LIS of this sequence, and ALL LIS's. Again, this can be through console output, or a GUI.

Note: I will accept this assignment up to September 30, without lateness penalty. However, you will need to be prepared to answer algorithmic questions concerning LIS on the quiz given September 28.