The Longest Increasing Subsequence, At Scale
Given n integers, print the length of the longest STRICTLY increasing subsequence. The
chosen values need not be adjacent, but must keep their original order.
10 9 2 5 3 7 101 18 -> 4 2 3 7 101 or 2 3 7 18
5 4 3 2 1 -> 1
## This is problem 452 with the limit raised
Problem 452 asks the same question with n up to a couple of thousand, where the O(n^2)
table is the right answer:
dp[i] = 1 + max over j < i with a[j] < a[i] of dp[j]
Here n reaches 200000 and that is 4 * 10^10 comparisons.
The table is not wrong. It is too slow, and the fix is a different algorithm rather than a different recurrence. Solve 452 first if you have not: this problem is only interesting once the quadratic version is familiar.
## Keep the best tail for each length
Maintain an array tails, where tails[L] is the SMALLEST value that can end an increasing
subsequence of length L + 1 seen so far.
For each value x:
find the first position p with tails[p] >= x
if p is past the end: append x
otherwise: tails[p] = x
The answer is the final length of tails.
## Two things to be clear about
FIRST, tails is always sorted in increasing order. That is what makes the position findable
by binary search, and it is why each value costs O(log n) rather than O(n).
It stays sorted because each step replaces exactly one entry with something no larger, and the
entry it replaces is the first one at least x, so the value before it is strictly smaller.
SECOND, tails is NOT the answer subsequence. It often is not a subsequence of the input at
all. On 2 6 8 3 4 5 1 it ends as 1 3 4 5, and the only 1 in the input is the LAST value,
so nothing can follow it. The true answer of length 4 is 2 3 4 5. Only the LENGTH of
tails is meaningful.
That distinction matters, because reconstructing the actual subsequence needs a separate array
of predecessors, and printing tails is a natural and wrong way to attempt it.
## Strictly increasing
Use the FIRST position with tails[p] >= x, which is a lower bound. Using the first position
strictly greater instead allows equal values and answers the non-decreasing question.
2 2 2 2 answers 1 and is the test that separates the two.
## Cost
Time O(n log n). Space O(n).