Longest increasing subsequence

Given a sequence $x_1,\ldots,x_N,$ we are to find the maximum length of a non-decreasing subsequence. Recall that a subsequence does not need to be contiguous (that would be a substring).

For example, the longest increasing subsequence of “1, 100, 2, 101, 3” is “1, 2, 3,” which has a length of 3.

One way to solve this is by defining $M(k)$ to be the maximum length of an increasing subsequence ending at, and including, the $k$th element. We can fill out $M(k)$ in order of increasing $k,$ and each update takes $O(N)$ time. Therefore, this solution takes a total of $O(N^2)$ time.

There is an $O(N\log N)$ solution, but it's harder to come up with. Once you know the answer you can prove it correct, though.

The idea is to iterate over $x_i$ in order and maintain an auxilliary array $A.$ At each step, if $x_i$ is strictly greater than the last element of $A,$ then append $x_i$ to the end of $A.$ Otherwise, use binary search to find the first element in $A$ which is strictly greater than $x_i,$ and replace that element with $x_i.$ After processing all $x_i,$ the length of $A$ is the length of the maximum increasing subsequence.

You can show the correctness of this algorithm with the following loop invariants:

• After processing $x_1, \ldots, x_i,$ the $\ell$th element of $A$ is the smallest $x_k$ such that $x_k$ is the last element of a length-$\ell$ increasing subsequence of $x_1,\ldots x_i.$
• $A$ is increasing.
• After processing $x_1, \ldots, x_i,$ the length of $A$ is the length of the longest increasing subsequence of $x_1,\ldots,x_i.$

The second loop invariant allows you to use binary search at each step. With a little thought you can convince yourself or your interviewer that these conditions are preserved at every step.