LeetCode 300 · Medium · 1-D Dynamic Programming

Longest Increasing Subsequence

Pick numbers from nums, keeping their order but skipping any you like, so that each pick is strictly larger than the last. Return the most numbers you can pick.

O(n²)time
O(n)space
LIS[i]longest run starting at i

comma-separated integers · 1–12 values · −999 to 999 each

nums

LIS LIS[i] = longest increasing subsequence that starts at nums[i] · filled right to left

public int lengthOfLIS(int[] nums) { int n = nums.length; int[] LIS = new int[n]; Arrays.fill(LIS, 1); for (int i = n - 1; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (nums[i] < nums[j]) { LIS[i] = Math.max(LIS[i], 1 + LIS[j]); } } } return Arrays.stream(LIS).max().getAsInt();}
i
—
j
—
nums[i], nums[j]
—
LIS[i]
—

Why it works

  1. Brute force tries every subsequence: 2ⁿ of them, each checked in O(n).
  2. Fix the first pick: an increasing subsequence starting at i either stops there (length 1) or continues at some later j with nums[j] > nums[i]. So LIS[i] = 1 + max(LIS[j]) over those j. The arc from LIS[j] into LIS[i] is that continuation.
  3. Two nested loops: each i scans every j to its right, and those cells are already final because the outer loop runs right to left. About n²/2 comparisons: O(n²) time, O(n) space.
  4. Pitfall: the answer is max(LIS), not LIS[0]: the best subsequence need not start at index 0. And "increasing" is strict, so [7,7,7] gives 1.
  5. Follow-up, O(n log n): keep tails[k], the smallest possible last value of an increasing subsequence of length k + 1, and binary-search where each number goes (patience sorting).