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 we drive down a major street in any city, we drive through a sequence of intersections with traffic lights, but we only have to stop at a subsequence of those intersections, where the traffic lights are red. If we’re lucky, we never stop at all: the empty sequence is a subsequence of $S$. On the other hand, if we’re unlucky, we 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 SUBSEQUENCEBACKTRACKING, but the strings QUEUE, 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’re 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$.