Longest Increasing Subsequence–Alternate Algorithm

Understand the various techniques used to solve the longest increasing subsequence–alternate algorithm problem efficiently.

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 S.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 very lucky, we never stop at all: the empty sequence is a subsequence of SS. On the other hand, if we’re very 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 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]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