The Tails Array Lies

O(nlog⁡n)O(n \log n) longest increasing subsequence on a = [3, 1, 4, 1, 5, 9, 2, 6].

vector<int> tails;
for (int x : a) {
    auto it = lower_bound(tails.begin(), tails.end(), x);
    if (it == tails.end()) tails.push_back(x);
    else *it = x;
}
// answer = tails.size()
after element tails
3 [3]
1 [1]
4 [1, 4]
1 [1, 4]
5 [1, 4, 5]
9 [1, 4, 5, 9]

What is tails after the last two elements, and what does it represent?

A

[1, 2, 5, 9], length 4, since 6 is smaller than 9 and is discarded.

B

[1, 2, 5, 6], length 4, and it is not a subsequence of the input.

C

[1, 2, 5, 6], length 4, and it is one of the longest increasing subsequences.

D

[1, 4, 5, 9], length 4, since 2 and 6 are both too small to extend it.