Skip to main content

Pattern 10: Longest Increasing Subsequence (LIS)

The Ordering Pattern: Find longest subsequence where elements follow increasing order. Can be extended to multidimensional problems.

The Core Pattern​

THE MENTAL MODEL

Imagine selecting cards from a deck to form the longest ascending sequence:

  1. Process elements left to right
  2. At each element, decide: include it or skip it
  3. If including, must be greater than previous elements
  4. Track longest sequence ending at each position
  5. Can use O(n²) DP or O(n log n) binary search

This is LIS.

Pattern Recognition​

WHEN YOU SEE THIS PATTERN

Keywords: "longest increasing", "ascending", "subsequence", "ordering"

Structure:

  • Array/sequence
  • Need to find longest ordered subsequence
  • Elements don't need to be consecutive

State:

  • dp[i] = "length of LIS ending at index i"
  • OR binary search with active candidates

Transitions:

  • For each j < i: if nums[j] < nums[i], can extend
  • dp[i] = max(dp[j] + 1) for all valid j

Common Problems​

  • Longest Increasing Subsequence
  • Number of Longest Increasing Subsequence
  • Russian Doll Envelopes (2D LIS)
  • Maximum Length of Pair Chain
  • Largest Divisible Subset
  • Longest String Chain

(Example problems will be added here)