The Tails Array Lies
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?
Sign in to answer questions and track your progress
Sign In