LIS (Patience Trick)
O(n log n)Longest strictly increasing subsequence. tails[k] holds the smallest possible last element of an increasing subsequence of length k+1; each new element replaces the first tail that is >= it (binary search), or extends the array. The tails array is always sorted, which is what makes the binary search valid, but note it is NOT itself the subsequence. Use lower_bound for strictly increasing, upper_bound to allow ties.
// use it on
CSES: Increasing Subsequence ↗
The template verbatim: read the array, print lis(a). n is 2·10^5, so the O(n²) table DP would time out.
// the code
int lis(vector<int>& a) {
vector<int> tails; // tails[k] = smallest tail of an LIS of length k+1
for (int x : a) {
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) tails.push_back(x);
else *it = x;
}
return tails.size();
}
// to recover one LIS, also record for each element the length it achieved,
// then walk backwards taking the first element with length L, L-1, ...// more classics