# 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 $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$.

Create a free account to access the full course.

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