Longest Increasing Subsequence—Alternate Algorithm

Subsequences and substrings

For any sequence SS, a subsequence of SS is another sequence obtained from SS by deleting zero or more elements without changing the order of the remaining elements; the elements of the subsequence need not be contiguous in SS. 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 SS. On the other hand, if we’re unlucky, we may have to stop at every intersection: SS 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]A[1..n], and we need to compute the longest possible sequence of indices 1i1<i2<<iln1 ≤ i_1 < i_2 < ··· < i_l ≤ n such that A[ik]<A[ik+1]A[i_k] < A[i_k+1] for all kk.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy