Longest Increasing Sequence

 

Hopefully, a pattern is emerging. Every dynamic programming solution has three components:  

1. Formulate the answer as a recurrence relation or recursive algorithm.
2. Show that the number of different values of your recurrence is bounded by a (hopefully small) polynomial.
3. Specify an order of evaluation for the recurrence so you always have the partial results you need available when you need them.

To see how this is done, let's see how we would develop an algorithm to find the longest monotonically increasing sequence in a sequence of n numbers. This problem arises in pattern matching on permutations, as described in Section . We distinguish an increasing sequence from a run, in that the selected elements need not be neighbors of each other. The selected elements must be in sorted order from left to right. For example, consider the sequence

The longest increasing subsequence of has length 3 and is either (2,3,4) or (2,3,6). The longest increasing run is of length 2, either (2,8) or (1,6).

Finding the longest increasing run in a numerical sequence is straightforward, indeed you should be able to devise a linear-time algorithm fairly easily. However, finding the longest increasing subsequence is considerably trickier. How can we identify which scattered elements to skip? To apply dynamic programming, we need to construct a recurrence computing the length of the longest sequence. To find the right recurrence, ask what information about the first n-1 elements of S, coupled with the last element , would enable you to find the answer for the entire sequence?

• The length of the longest increasing sequence in seems a useful thing to know. In fact, this will be the longest increasing sequence in S, unless extends it or another increasing sequence of the same length. Unfortunately, knowing just this length is not enough. Suppose I told you that the longest increasing sequence in was of length 5 and that . Will the length of the final longest increasing subsequence of S be 5 or 6?
• Therefore, we also need the length of the longest sequence that will extend. To be certain we know this, we really need the length of the longest sequence that any possible number can extend.

This provides the idea around which to build a recurrence. Define to be the length of the longest sequence ending with . Verify that the following table is correct:

9 5 2 8 7 3 1 6 4

1 1 1 2 2 2 1 3 3

- - - 2 2 3 - 6 6

The longest increasing sequence containing the nth number will be formed by appending it to the longest increasing sequence to the left of n that ends on a number smaller than . The following recurrence computes :

These values define the length of the longest increasing sequence ending at each number. The length of the longest increasing subsequence of the entire permutation is given by , since the winning sequence will have to end somewhere.

What is the time complexity of this algorithm? Each one of the n values of is computed by comparing against up to values to the left of it, so this analysis gives a total of time. In fact, by using dictionary data structures in a clever way, we can evaluate this recurrence in time. However, the simple recurrence would be easy to program and therefore is a good place to start.

What auxiliary information will we need to store in order to reconstruct the actual sequence instead of its length? For each element , we will store the index of the element that appears immediately before in the longest increasing sequence ending at . Since all of these pointers go towards the left, it is a simple matter to start from the last value of the longest sequence and follow the pointers so as to reconstruct the other items in the sequence.