Skip to main content
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)

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

LIS of [10,9,2,5,3,7,101,18]
10
0
9
1
2
2
5
3
3
4
7
5
101
6
18
7
dp[1,1,1,1,1,1,1,1]
1/3

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.