Longest Increasing Subsequence

At a glance

The instinct

A subsequence keeps the original order but may skip elements. When the question is "longest chain where every next element is strictly greater / later / fits inside the previous one," you are looking at LIS or a dressed-up version of it.

Start with the honest DP: dp[i] = length of the longest increasing subsequence ending at index i. Every earlier j with a[j] < a[i] is a candidate predecessor, so dp[i] = 1 + max(dp[j]). That is O(n²) and often enough. When n reaches 10⁵, switch to the tails trick: keep, for every length L, the smallest possible tail value of an increasing subsequence of length L, and update it with binary search.

Recognise it

Not this pattern if...

• The elements must be contiguous: a single scan or sliding window does it in O(n).
• You compare two sequences: that is LCS (string DP).
• You only need to know if an increasing triplet exists: a two-variable greedy suffices (Increasing Triplet Subsequence).

Memory hack

DP framing (O(n²) version): state dp[i] = longest chain ending exactly at i; choice = which earlier j to attach to; base case dp[i] = 1 (the element alone); order = left to right, and the answer is max(dp), not dp[n-1].

Analogy: think of the tails array as a podium of record-holders: "shortest-tail champion for length 1, length 2, ...". A new number either sets a new length record (append) or lowers the bar for some existing length (replace), making future extensions easier.

Say it out loud in the interview:

1. "dp[i] is the best chain ending at i; I look back at every smaller element - O(n²)."
2. "To speed up, tails[L] is the smallest end of any chain of length L+1; it stays sorted, so binary search."
3. "Tails is not the actual subsequence - only its length is meaningful; I need parent pointers to rebuild it."

How it works

For each number x, binary-search the first tail ≥ x (lower bound). If x is bigger than every tail it extends the longest chain; otherwise it replaces that tail, keeping the same length but with a smaller ending.

Trace on [10, 9, 2, 5, 3, 7, 101, 18]:

Answer: 4 (for example 2, 3, 7, 18).

Java template

import java.util.*;

class LongestIncreasing {
    // O(n^2): length AND number of LIS. Change the comparison for custom "can follow" rules.
    static int[] lisLengthAndCount(int[] a) {
        int n = a.length, best = 0, ways = 0;
        int[] len = new int[n], cnt = new int[n];
        for (int i = 0; i < n; i++) {
            len[i] = 1; cnt[i] = 1;                   // base: element alone
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i]) {                    // problem-specific "j can precede i"
                    if (len[j] + 1 > len[i]) { len[i] = len[j] + 1; cnt[i] = cnt[j]; }
                    else if (len[j] + 1 == len[i]) cnt[i] += cnt[j];
                }
            }
            if (len[i] > best) { best = len[i]; ways = cnt[i]; }
            else if (len[i] == best) ways += cnt[i];
        }
        return new int[]{best, ways};
    }

    // O(n log n) length only. strict=true for strictly increasing, false for non-decreasing.
    static int lisLength(int[] a, boolean strict) {
        int[] tails = new int[a.length];
        int size = 0;
        for (int x : a) {
            int lo = 0, hi = size;                    // search in tails[0..size)
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                boolean goRight = strict ? tails[mid] < x : tails[mid] <= x;
                if (goRight) lo = mid + 1; else hi = mid;
            }
            tails[lo] = x;                            // replace or append
            if (lo == size) size++;
        }
        return size;
    }

    // 2-D nesting: sort width ascending, height DESCENDING on ties, then LIS on heights.
    static int maxNesting(int[][] env) {
        Arrays.sort(env, (p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0]) : Integer.compare(q[1], p[1]));
        int[] h = new int[env.length];
        for (int i = 0; i < env.length; i++) h[i] = env[i][1];
        return lisLength(h, true);
    }
}

Complexity

Variations

• Plain length: Longest Increasing Subsequence - either approach; mention both and their trade-off.
• Counting: Number of Longest Increasing Subsequence - keep len[] and cnt[]; on a tie in length, add counts instead of replacing.
• 2-D nesting: Russian Doll Envelopes - sort by width ascending and height descending for equal widths, then strict LIS on heights.
• Divisibility chain: Largest Divisible Subset - sort, use a[i] % a[j] == 0 as the predecessor test, keep parent pointers to output the set.
• Word chains: Longest String Chain - sort by length; predecessor is any word formed by deleting one character (hash map lookup).
• Non-decreasing variant: allow equal neighbours by using upper bound (first tail > x) instead of lower bound.
• Bitonic / mountain: Minimum Number of Removals to Make Mountain Array - LIS from the left plus LIS from the right at each peak.

Common mistakes

• Returning dp[n-1]. The longest chain need not end at the last element; return the maximum over all i.
• Lower vs upper bound mix-up. Strictly increasing uses "first ≥ x"; non-decreasing uses "first > x". Getting it wrong miscounts duplicates.
• Ascending tie-break in Russian Doll Envelopes. Equal widths sorted by ascending height let two same-width envelopes nest; sort heights descending on ties.
• Counting LIS with the tails method. Counting needs the O(n²) DP (or a Fenwick tree); tails loses the information.
• Forgetting the base case dp[i] = 1, which leaves single elements at length 0.

All practice problems

3 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.