templates · Dynamic programming

Longest increasing subsequence

  • "Longest increasing (or non-decreasing) subsequence": items may be skipped, order must stay
  • Chains or nesting: envelopes, boxes, pairs where each must be bigger than the last
  • n up to about 10⁵, so O(n²) is too slow and you need the O(n log n) version

Longest increasing subsequenceBinary search (exact & bounds)

the one rule

The invariant

tails stays sorted, and tails[k] is the smallest last value of any increasing subsequence of length k + 1 seen so far.

write it from memory

The template

O(n²) DP

javajava.util.*
/** Length of the longest strictly increasing subsequence, the O(n²) DP. */static int lisQuadratic(int[] nums) {    int n = nums.length;    int[] dp = new int[n];                               // dp[i] = longest increasing subsequence that ENDS at i    int best = 0;    for (int i = 0; i < n; i++) {        dp[i] = 1;                                       // base case: nums[i] alone        for (int j = 0; j < i; j++) {            if (nums[j] < nums[i]) {                     // can nums[i] extend the one ending at j?                dp[i] = Math.max(dp[i], dp[j] + 1);            }        }        best = Math.max(best, dp[i]);                    // the answer may end anywhere    }    return best;}

dp[i] is the best subsequence that ends at i, so the answer is the max over all i, not dp[n - 1].

fill in the blanks — only these lines change per problem

  1. line 9When nums[i] may follow nums[j]: < for strictly increasing, <= for non-decreasing, or a pair rule.
  2. line 13Track the max over every end index, because the best subsequence can end anywhere.

O(n log n) with lower bound

javajava.util.*
/** Same answer in O(n log n): tails[k] = smallest possible last value of an increasing subsequence of length k + 1. */static int lisTails(int[] nums) {    int[] tails = new int[nums.length];    int size = 0;                                        // tails[0..size-1] is sorted    for (int x : nums) {        int lo = 0, hi = size;                           // lower bound: first tail >= x        while (lo < hi) {            int mid = lo + (hi - lo) / 2;            if (tails[mid] < x) lo = mid + 1;            // `<` = strictly increasing            else hi = mid;        }        tails[lo] = x;                                   // x is a smaller end for length lo + 1        if (lo == size) size++;                          // x extended the longest one    }    return size;}

tails is not the subsequence itself, only its length is right. Each new value either grows the list or makes some end smaller.

fill in the blanks — only these lines change per problem

  1. line 9tails[mid] < x (lower bound) for strictly increasing; <= x (upper bound) for non-decreasing.
  2. line 12Put x at the found position; this keeps every length's end as small as possible.

complexity

What it costs

time O(n²), or O(n log n)
The DP compares every pair (j, i). The tails version does one binary search (log n) per element instead.
space O(n)
One dp value or one tail per element.

watch out

Common bugs

  • Returning dp[n - 1] instead of the max of all dp[i].
  • Using upper bound when the problem wants strictly increasing. Duplicates then count as increasing.
  • Printing tails as if it were the actual subsequence. It is not; rebuild with parent links if you need the elements.

use it

Practise it on

learn it properly