uniolympiads Ελληνικά

Longest increasing subsequence

Its length in O(nlog⁡n)O(n \log n), 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 fi=1+max⁡j<i, aj<aifjf_i = 1 + \max_{j < i,\ a_j < a_i} f_j is O(n2)O(n^2). For n=2⋅105n = 2 \cdot 10^5 we need something better.

Keep tailk\mathrm{tail}_k: the smallest last element among all increasing subsequences of length k+1k+1 seen so far. The array tail\mathrm{tail} is strictly increasing. For each new xx, the first tailk≥x\mathrm{tail}_k \ge x is replaced by xx: a subsequence of length kk ending in something <x< x is extended by xx. If there is no such kk, xx makes the array one longer. The answer is the length of the array.

Pitfalls

  • tail\mathrm{tail} 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.

cpp/lis.cpp
// 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.

More in the USACO Guide

In English, with more problems per level.