next up previous contents index CD CD Algorithms
Next: Minimum Weight Triangulation Up: Dynamic Programming Previous: Approximate String Matching

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 gif. 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 tex2html_wrap_inline24622 , would enable you to find the answer for the entire sequence?

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

sequence tex2html_wrap_inline24638 9 5 2 8 7 3 1 6 4
length tex2html_wrap_inline24640 1 1 1 2 2 2 1 3 3
predecessor tex2html_wrap_inline24642 - - - 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 tex2html_wrap_inline24644 . The following recurrence computes tex2html_wrap_inline24646 :


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 tex2html_wrap_inline24648 , since the winning sequence will have to end somewhere.

What is the time complexity of this algorithm? Each one of the n values of tex2html_wrap_inline24650 is computed by comparing tex2html_wrap_inline24652 against up to tex2html_wrap_inline24654 values to the left of it, so this analysis gives a total of tex2html_wrap_inline24656 time. In fact, by using dictionary data structures in a clever way, we can evaluate this recurrence in tex2html_wrap_inline24658 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 tex2html_wrap_inline24660 , we will store the index tex2html_wrap_inline24662 of the element that appears immediately before tex2html_wrap_inline24664 in the longest increasing sequence ending at tex2html_wrap_inline24666 . 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.

next up previous contents index CD CD Algorithms
Next: Minimum Weight Triangulation Up: Dynamic Programming Previous: Approximate String Matching

Mon Jun 2 23:33:50 EDT 1997