Warm-up Coding Interview: Dynamic Programming

Longest Increasing Sequence

There are three steps involved in solving a problem by dynamic programming:

  1. Formulate the answer as a recurrence relation or recursive algorithm.
  2. Show that the number of different parameter values taken on by your recurrence is bounded by a (hopefully small) polynomial.
  3. Specify an order of evaluation for the recurrence so the partial results you need are always 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 subsequence within a sequence of n numbers. Still, it is instructive to work it out from scratch. Indeed, dynamic programming algorithms are often easier to reinvent than look up.

We distinguish an increasing sequence from a run, where the elements, must be physical neighbors of each other. The selected elements of both must be sorted in increasing order from left to right. For example, consider the sequence

The longest increasing subsequence of S has length 5, including {2, 3, 5, 6, 8}. In fact, there are eight of this length (can you enumerate them?).

Finding the longest increasing run in a numerical sequence is strightforward. Indeed, you should longest increasing subsequence is considerably tricker. How can we identify which scattered elements to skip? To apply dynamic programming, we need to construct a recurrence that computes the length of the longest sequence. To find the right recurrence, ask what information about the first n-1 elements of S would help you to find the answer for the entire sequence?

  • The length of the longest increasing sequence in s_1, s_2, \cdots, s_{n-1} seems a useful thing to know. In fact, this will be longest increasing sequence in S, unless s_n extends some increasing sequence of the same length.

Unfortunately, the length of this sequence is not enough information to complete the full solution. Suppose I told you that the longest increasing sequence in s_1, s_2, \dots, s_{n-1} was of length 5 and that s_n = 9. Will the length of the final longest increasing subsequence of S be 5 or 6?

  • We need to know the length of the longest sequence that s_n will extend. To be certain we know this, we really need the length of the longest sequence that any possible value of s_n can extend.

This provides the idea around which to build a recurrence. Define l_i to be the length of the longest sequence ending with s_i.

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 s_n. The following recurrence computes l_i:

l_i = \max_{0<j<i} l_j + 1, \text{ where } (s_j < s_i),

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

In fact, by using dictionary data structures in a clever way, we can evaluate this recurrence in O(n lg n) time. However, the simple recurrence would be easy to program and therefore is a good place to start.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.