Longest Increasing Subsequence

Description

The task: given a sequence, find the longest subsequence, not necessarily contiguous, whose values strictly increase. Variants ask for the heaviest such subsequence, or the longest chain of nested boxes. Trying all 2^n subsequences is hopeless. The DP insight is to ask a narrower question at each position: what's the best subsequence that ends exactly here? That gives an O(n²) DP, and a "tails" array brings the length down to O(n log n).

We'll go from simple to more technical:

1. The pattern: dp[i] = the longest increasing subsequence ending at i.
2. A second flavor: O(n log n) with the tails array and binary search.
3. Where LIS shows up (version diffs, nesting, scheduling).
4. What breaks it: reading the answer from the wrong place, tails mistaken for the answer, strict vs non-strict.

The approach

int lengthOfLIS(int[] nums) {
    int n = nums.length, best = 1;
    int[] dp = new int[n];                     // dp[i] = longest increasing subsequence ENDING at i
    for (int i = 0; i < n; i++) {
        dp[i] = 1;                             // nums[i] on its own
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);   // extend a chain ending at j
        }
        best = Math.max(best, dp[i]);          // the answer can end anywhere
    }
    return best;
}

def length_of_lis(nums: list[int]) -> int:
    n, best = len(nums), 1
    dp = [1] * n                                # dp[i] = longest increasing subsequence ENDING at i
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)   # extend a chain ending at j
        best = max(best, dp[i])                 # the answer can end anywhere
    return best

Fixing the last element makes the recurrence easy: a chain ending at i is some chain ending at an earlier, smaller value, plus nums[i]. The answer is the maximum over every i - on [1, 2, 0], dp at the last index is 1, but the answer is 2. Changing the combine step gives relatives: dp[j] + nums[i] with base nums[i] finds the maximum-sum increasing subsequence.

A second flavor: O(n log n) with tails

For the length alone, keep tails[k] = the smallest possible last value of an increasing subsequence of length k + 1. A smaller tail is never worse - it leaves more room to extend. Each value replaces the first tail that is >= it, or extends the list:

int[] tails = new int[n];
int len = 0;
for (int x : nums) {
    int lo = 0, hi = len;
    while (lo < hi) { int mid = (lo + hi) >>> 1; if (tails[mid] < x) lo = mid + 1; else hi = mid; }
    tails[lo] = x;                             // x becomes the best tail for length lo + 1
    if (lo == len) len++;
}
return len;

from bisect import bisect_left


def length_of_lis(nums: list[int]) -> int:
    tails = []
    for x in nums:
        i = bisect_left(tails, x)               # the first tail >= x
        if i == len(tails):
            tails.append(x)                     # x extends the longest chain
        else:
            tails[i] = x                        # x becomes the best tail for length i + 1
    return len(tails)

tails stays sorted, so each step is a binary search: O(n log n) - about 1.7 million steps for n = 10^5, against 5 billion for the quadratic loop. Two cautions: tails is not an actual subsequence (for [3, 4, 1] it ends as [1, 4]), and "strictly increasing" needs the first tail >= x; for non-decreasing, search for the first tail > x ([2, 2, 2] then has length 3, not 1). In Python, bisect.bisect_left(tails, x) is exactly "the first tail >= x", and bisect_right the first tail > x. Nested envelopes reduce to this: sort by width ascending and, for equal widths, height descending, then run LIS on heights - the descending tie-break stops two envelopes of the same width from both joining a chain.

Where you'll see it

Longest-increasing-subsequence logic shows up in version-control and patience diff algorithms (matching unique lines in order), in scheduling chains of compatible tasks, in stacking and nesting problems (boxes, envelopes), and in measuring how "sorted" a sequence already is - n minus the LIS is the minimum number of elements to move to make it sorted.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why is the answer max(dp[i]) and not dp[n - 1]?

2. After running the tails method on [3, 4, 1], tails is [1, 4]. Is that an increasing subsequence of the input?

3. For nested envelopes, why sort equal widths by height descending before running LIS on heights?

Key takeaways

• dp[i] = best subsequence ending exactly at i; extend from every compatible earlier j; the answer is the max over all i.
• O(n^2) and flexible: swap the combine step for sums, counts or custom compatibility.
• For the length: tails + binary search, O(n log n); tails is not the subsequence itself.
• Strictly increasing uses the first tail >= x; non-decreasing uses the first tail > x.
• 2D chains (envelopes) reduce to LIS after sorting by one dimension, with a descending tie-break.