LIS Pattern

LIS O(n²)

dp[i] = length of longest increasing subsequence ending at index i. For each i, check all j < i: if nums[j] < nums[i], then dp[i] = max(dp[i], dp[j] + 1). Answer = max of all dp values.

O(n²)

O(n)

say this out loud

The straightforward version is O(n squared): for each element, look back for the best smaller predecessor.

How It Works

The quadratic LIS solution defines dp[i] as the length of the longest strictly increasing subsequence that ends exactly at index i. To compute it, scan every earlier index j: whenever nums[j] < nums[i], the subsequence ending at j can be extended by nums[i], so dp[i] = max(dp[i], dp[j] + 1). Every element starts with dp[i] = 1 (itself), and the final answer is the maximum over all endings, not dp[n-1].

Checking all pairs gives O(n^2) time and O(n) space, a huge improvement over testing 2^n subsequences, and easy to adapt. Changing max-length to max-sum, adding pair counts, or replacing the comparison (divisibility, string chaining) turns this template into a family of problems.

Step-by-Step Visualization

nums = [10, 9, 2, 5, 3, 7, 101, 18]. dp[i] = longest increasing run ending at i

101

dpall start at 1

1/10

Code

Java

static int lengthOfLIS(int[] nums) {
  int[] dp = new int[nums.length];
  Arrays.fill(dp, 1);

  for (int i = 1; i < nums.length; i++)
    for (int j = 0; j < i; j++)
      if (nums[j] < nums[i])
        dp[i] = Math.max(dp[i], dp[j] + 1);

  int max = 0;
  for (int v : dp) max = Math.max(max, v);
  return max;
}
// lengthOfLIS(new int[]{10,9,2,5,3,7,101,18}) → 4

Tips & Gotchas

1dp[i] = length of LIS ending at index i

2For each i, check all j < i: if nums[j] < nums[i], dp[i] = max(dp[i], dp[j]+1)

3Answer is max of all dp values

Practice Problems

1Longest Increasing Subsequence
2Number of Longest Increasing Subsequence
3Largest Divisible Subset
4Maximum Sum Increasing Subsequence
5Longest String Chain

About the LIS Pattern Pattern

Find the longest subsequence where every element is larger than the previous. Classic DP: for each element, find the longest increasing subsequence ending there. Can be optimized from O(n²) to O(n log n) with binary search.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

Climbing Stairs
Coin Change
Longest Common Subsequence
0/1 Knapsack
Edit Distance
House Robber
Longest Increasing Subsequence
Word Break

Frequently Asked Questions

Why is the answer max over all dp[i] rather than dp[n-1]?

dp[i] is defined as the best subsequence ending at i, and the longest one may end anywhere in the array. Forgetting the final max scan is a common bug. Dp[n-1] only covers subsequences that end with the last element.

When should I prefer the O(n^2) version over the O(n log n) one?

Use the quadratic version when you need more than the length: counting the number of LIS, maximizing a sum, or reconstructing with tie-breaking all fit naturally into the pairwise formulation. The binary-search version tracks only tails and loses that structure.

How do I make LIS non-strict, allowing equal elements?

Relax the comparison from nums[j] < nums[i] to nums[j] <= nums[i]. In the patience-sorting variant the equivalent change is switching from lower_bound to upper_bound when placing each element.