Longest Increasing Subsequence—Alternate Algorithm

Subsequences and substrings

For any sequence S, a subsequence of S is another sequence obtained from S by deleting zero or more elements without changing the order of the remaining elements; the elements of the subsequence need not be contiguous in S. For example, when you drive down a major street in any city, you drive through a sequence of intersections with traffic lights, but you only have to stop at a subsequence of those intersections, where the traffic lights are red. If you’re very lucky, you never stop at all: the empty sequence is a subsequence of S. On the other hand, if you’re very unlucky, you may have to stop at every intersection: S is a subsequence of itself.

As another example, the strings BENT, ACKACK, SQUARING, and SUBSEQUENT are all subsequences of the string SUBSEQUENCEBACKTRACKING, as are the empty string and the entire string SSUBSEQUENCEBACKTRACKING, but the strings QUEUE and EQUUS and TALLYHO are not. A subsequence whose elements are contiguous in the original sequence is called a substring; for example, MASHER and LAUGHTER are both subsequences of MANSLAUGHTER, but only LAUGHTER is a substring.

Now suppose we are given a sequence of integers, and we need to find the longest subsequence whose elements are in increasing order. More concretely, the input is an integer array $A[1..n]$, and we need to compute the longest possible sequence of indices $1 ≤ i_1 < i_2 < ··· < i_l ≤ n$ such that $A[i_k] < A[i_k+1]$ for all k.

Approach to building longest increasing subsequence

One natural approach to building this longest increasing subsequence is to decide, for each index $j$ in order from $1$ to $n$, whether or not to include $A[j]$ in the subsequence. Jumping into the middle of this decision sequence, we might imagine the following picture:

As in our earlier text segmentation examples, the black bar separates our past decisions from the portion of the input we have not yet processed. Numbers we have already decided to include are highlighted and bolded; numbers we have already decided to exclude are grayed out. (Notice that the numbers we’ve decided to include are increasing!) Our algorithm must decide whether or not to include the number immediately after the black bar.

In this example, we definitely cannot include 5 because then the selected numbers would no longer be in increasing order. So let’s skip ahead to the next decision:

Backtracking algorithm for longest increasing subsequence

Now we can include 8, but it’s not obvious whether we should. Rather than trying to be “smart,” our backtracking algorithm will use simple brute force.

• First tentatively include the 8, and let the Recursion Fairy make the rest of the decisions.
• Then tentatively exclude the 8, and let the Recursion Fairy make the rest of the decisions.

Whichever choice leads to a longer increasing subsequence is the right one. (This is precisely the same recursion pattern we used to solve $SubsetSum$.)

Now for the key question: What do we need to remember about our past decisions? We can only include $A[j]$ if the resulting subsequence is in increasing order. If we assume (inductively!) that the numbers previously selected from $A[1 .. j − 1]$ are in increasing order, then we can include $A[ j]$ if and only if $A[ j]$ is larger than the last number selected from $A[1 .. j − 1]$. Thus, the only information we need about the past is the last number selected so far. We can now revise our pictures by erasing everything we don’t need:

So the problem our recursive strategy is actually solving is the following:

As usual, our recursive strategy requires a base case. Our current strategy breaks down when we get to the end of the array because there is no “next number” to consider. But an empty array has exactly one subsequence, namely, the empty sequence. Vacuously, every element in the empty sequence is larger than whatever value you want, and every pair of elements in the empty sequence appears in increasing order. Thus, the longest increasing subsequence of the empty array has length 0.

Here’s the resulting recursive algorithm:

$$\begin{gathered} \underset{‾}{LISbigger(prev,A[\mathrm{1..}n]):} \\ ifn=0 \\ return0 \\ elseifA[1]\le prev \\ returnLISbigger(prev,A[\mathrm{2..}n) \\ else \\ skip\leftarrow LISbigger(prev,A[\mathrm{2..}n]) \\ take\leftarrow LISbigger(A[1],A[\mathrm{2..}n])+ \end{gathered}$$ ...