Lesson 31.1 · DP on Strings and Sequences

Longest Increasing Subsequence

O(n²): dp[i] = 1 + max dp[j] over j < i with a smaller value. O(n log n): keep the smallest possible tail for each length and binary search where each new value goes.

16 min

Think of it like this

Dealing cards into piles where each card goes on the leftmost pile whose top card is at least as large (patience solitaire). The number of piles you end with is the length of the longest increasing run you could pick out.

1.Two solutions

Quadratic DP: dp[i] = length of the longest increasing subsequence ending at i = 1 + max(dp[j]) over j < i with nums[j] < nums[i]. The answer is the largest dp[i]. O(n²).

Tails array: tails[k] = the smallest possible last value of an increasing subsequence of length k + 1. It's always sorted, so for each x, binary search the first tail ≥ x and replace it (or append if x is larger than all). The array's length is the LIS length. O(n log n).

tails itself isn't necessarily a real subsequence; it records the best ending value for each length. To rebuild an actual LIS, store a parent index for each element.

Main.java

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int[] tails = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            int lo = 0, hi = size;
            while (lo < hi) {                       // first tail >= x
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < x) lo = mid + 1; else hi = mid;
            }
            tails[lo] = x;
            if (lo == size) size++;
            System.out.println(x + " -> " + Arrays.toString(Arrays.copyOf(tails, size)));
        }
        System.out.println("LIS length = " + size);
    }
}

Output

10 -> [10]
9 -> [9]
2 -> [2]
5 -> [2, 5]
3 -> [2, 3]
7 -> [2, 3, 7]
101 -> [2, 3, 7, 101]
18 -> [2, 3, 7, 18]
LIS length = 4

Remember

dp[i] = LIS ending at i.
tails[k] = smallest tail for length k + 1.
Strictly increasing: lower bound; non-decreasing: upper bound.

Common mistakes

Reporting tails as the subsequence.
Using the wrong bound for strict vs non-strict.

Words used in this lesson

Subsequence: Elements kept in order but not necessarily next to each other.
Substring / subarray: A contiguous piece.

Command Palette

Longest Increasing Subsequence

1.Two solutions