Longest increasing subsequence
Its length in , keeping for every length the smallest possible last element.
When
The direct application is rare. Much more often a problem reduces to LIS: sort pairs by one coordinate and look for an increasing sequence in the other (envelopes inside envelopes, towers of boxes).
The idea
The DP is . For we need something better.
Keep : the smallest last element among all increasing subsequences of length seen so far. The array is strictly increasing. For each new , the first is replaced by : a subsequence of length ending in something is extended by . If there is no such , makes the array one longer. The answer is the length of the array.
Pitfalls
- is not the subsequence itself. To reconstruct it, store for each element the index of its predecessor.
- Strictly increasing:
lower_bound. Non-decreasing:upper_bound. The test for this page has many equal values precisely to catch this.
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Length of the longest strictly increasing subsequence. O(n log n).
// tail[k] = the smallest possible last element of an increasing subsequence of length k + 1.
// tail stays sorted, so each element replaces the first tail >= it (lower_bound).
// For non-decreasing subsequences use upper_bound instead.
int lisLength(const vector<ll>& a) {
vector<ll> tail;
for (ll x : a) {
auto it = lower_bound(tail.begin(), tail.end(), x);
if (it == tail.end()) {
tail.push_back(x);
} else {
*it = x;
}
}
return tail.size();
}
Tested on 3,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- Increasing Subsequence · Dynamic Programming
More in the USACO Guide
- Longest Increasing Subsequence · usaco.guide/gold/lis
In English, with more problems per level.