Longest Increasing Sequence
There are three steps involved in solving a problem by dynamic programming:
- Formulate the answer as a recurrence relation or recursive algorithm.
- Show that the number of different parameter values taken on by your recurrence is bounded by a (hopefully small) polynomial.
- 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 [katex]s_1, s_2, \cdots, s_{n-1}[/katex] seems a useful thing to know. In fact, this will be longest increasing sequence in S, unless [katex]s_n[/katex] 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 [katex]s_1, s_2, \dots, s_{n-1}[/katex] was of length 5 and that [katex]s_n = 9[/katex]. 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 [katex]s_n[/katex] will extend. To be certain we know this, we really need the length of the longest sequence that any possible value of [katex]s_n[/katex] can extend.
This provides the idea around which to build a recurrence. Define [katex]l_i[/katex] to be the length of the longest sequence ending with [katex]s_i[/katex].
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 [katex]s_n[/katex]. The following recurrence computes [katex]l_i[/katex]:
[katex]l_i = \max_{0<j<i} l_j + 1, \text{ where } (s_j < s_i),[/katex]
What auxiliary information will we need to store to reconstruct the actual sequence instead of its length? For each element [katex]s_i[/katex], we will store its predecessor — the index [katex]p_i[/katex] of the element that appears immediately before [katex]s_i[/katex]. 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.