Longest increasing subsequence

You’ll recognise it when

• You pick elements in their original order (skipping any you like) and the picks must keep going up.
• The question asks for the fewest deletions that leave an array sorted: that’s n minus the LIS.
• Items nest or stack only if they’re bigger in two dimensions (envelopes, boxes, people on shoulders). Sort by one dimension and it becomes an LIS on the other.
• n is up to 10⁵, so the O(n²) DP is too slow and you need the O(n log n) version.

It’s easy to confuse with the longest increasing subarray, where the elements must be next to each other; that one is a single linear scan.

The idea

Deal a shuffled deck of numbered cards into piles, left to right. Each card goes on the leftmost pile whose top card is at least as big; if there is none, it starts a new pile on the right. The number of piles at the end is the length of the longest increasing run you could have picked from the deck. A small top card is good news: it lets more future cards land on the pile after it.

Start with the plain DP. Let dp[i] be the length of the longest increasing subsequence that ends at a[i]. It is 1 (just a[i]) plus the best dp[j] over earlier j with a smaller value. The answer is the largest dp[i], not the last one:

def lis_quadratic(a):
    dp = [1] * len(a)            # dp[i]: longest increasing run ending at a[i]
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

That’s O(n²): fine for a few thousand values, too slow for 10⁵. The fast version keeps less. For each length it remembers only the smallest value that can end a run of that length, in an array called tails. Among all runs of length 3, the one ending lowest is the easiest to extend, so it’s the only one worth keeping. tails is always sorted, which means binary search can find where each new value belongs.

How it works

Read the values left to right and update tails for each one. The graphic follows the steps as you scroll. Turn on quiz me to predict each slot yourself, or edit the array: try duplicates, or a decreasing run.

Why it’s correct: after each step, tails[k] is the smallest ending value of any increasing run of length k + 1 seen so far. A new x can extend every run whose end is below x; the longest such run has length pos, the number of tails smaller than x. So x ends a run of length pos + 1, and since tails[pos] >= x, x is the new smallest ending for that length. No other slot changes. tails only gets longer when a longer run exists, so its final length is the LIS.

def lis_length(a):
    """Length of the longest strictly increasing subsequence of a."""
    tails = []
    for x in a:
        # Lower bound: the first slot whose tail is >= x.
        lo, hi = 0, len(tails)
        while lo < hi:
            mid = (lo + hi) // 2
            if tails[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        pos = lo
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

#include <vector>
using namespace std;

// Length of the longest strictly increasing subsequence of a.
int lisLength(const vector<int>& a) {
    vector<int> tails;
    for (int x : a) {
        // Lower bound: the first slot whose tail is >= x.
        int lo = 0, hi = tails.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        int pos = lo;
        if (pos == (int)tails.size()) {
            tails.push_back(x);
        } else {
            tails[pos] = x;
        }
    }
    return tails.size();
}

class Lis {
    // Length of the longest strictly increasing subsequence of a.
    static int lisLength(int[] a) {
        int[] tails = new int[a.length];
        int len = 0;
        for (int x : a) {
            // Lower bound: the first slot whose tail is >= x.
            int lo = 0, hi = len;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (tails[mid] < x) lo = mid + 1;
                else hi = mid;
            }
            int pos = lo;
            if (pos == len) {
                tails[len++] = x;
            } else {
                tails[pos] = x;
            }
        }
        return len;
    }
}

The code keeps values only, which is all the length needs. To rebuild a sequence, keep indices in tails plus a parent array, as the graphic does:

from bisect import bisect_left

def lis_sequence(a):
    tails, tail_idx = [], []       # tail values, and where each came from
    parent = [-1] * len(a)
    for i, x in enumerate(a):
        pos = bisect_left(tails, x)
        if pos > 0:
            parent[i] = tail_idx[pos - 1]
        if pos == len(tails):
            tails.append(x); tail_idx.append(i)
        else:
            tails[pos] = x; tail_idx[pos] = i
    seq, i = [], tail_idx[-1] if a else -1
    while i != -1:
        seq.append(a[i]); i = parent[i]
    return seq[::-1]

Why it’s O(n log n)

Each of the n values does one binary search over tails, which has at most n entries: O(log n) per value, O(n log n) total. tails and the parent links take O(n) space.

The O(n²) DP is still worth knowing: it adapts easily when the rule isn’t just “smaller value”, for example counting runs or adding weights.

Common mistakes

return dp[-1]               # ✗ best run ending at the last value
return max(dp, default=0)   # ✓ best run ending anywhere

pos = bisect_right(tails, x)   # ✗ counts 2, 2, 2 as increasing
pos = bisect_left(tails, x)    # ✓ equal values replace, never extend

env.sort()                                  # ✗ (1,1), (1,2), (1,3) → 3
env.sort(key=lambda e: (e[0], -e[1]))       # ✓ heights 3, 2, 1 → 1

Variations

• Reconstructing the sequence. Store indices in tails and a parent for every element, then walk back from the last tail, as in the snippet above. With the O(n²) DP, record which j gave the best dp[i].
• Non-decreasing subsequence. Allow equal neighbours by using the upper bound (bisect_right, std::upper_bound) instead of the lower bound. CSES Towers is this in disguise: the fewest towers equals the longest non-decreasing run.
• Russian doll envelopes. Sort by width ascending and, for equal widths, height descending. Then the answer is the strict LIS of the heights.
• Number of LISs. Next to dp[i], keep count[i], the number of best runs ending at i: when dp[j] + 1 beats dp[i], copy count[j]; when it ties, add it. Sum the counts of every i with the maximum dp[i]. This is O(n²).
• Longest decreasing, and deletions. For a decreasing run, negate the values or reverse the comparison. The fewest deletions to leave an array strictly increasing is n minus its LIS.