Longest Increasing Subsequence (LC 300)

Pattern: 1-D DP — dp[i] = LIS ending at i. (Optional follow-up: Patience sorting in O(n log n).) Difficulty: Medium Key Concept: For each i, the LIS ending at i is 1 + max(dp[j] for j < i where nums[j] < nums[i]).

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence preserves relative order but may skip elements.

Example

nums = [10, 9, 2, 5, 3, 7, 101, 18] → 4 (one LIS: [2, 3, 7, 101])
nums = [0, 1, 0, 3, 2, 3] → 4
nums = [7, 7, 7, 7] → 1

1. Algorithm & Pseudocode

O(n²) DP

dp[i] = 1  for all i
for i = 0..n-1:
  for j = 0..i-1:
    if nums[j] < nums[i]:
      dp[i] = max(dp[i], dp[j] + 1)
return max(dp)

O(n log n) — Patience Sorting

Maintain an array tails, where tails[k] is the smallest tail value of any increasing subsequence of length k+1.

for x in nums:
  pos = binarySearch(tails, x)   // first index >= x
  if pos == tails.size:
    tails.add(x)
  else:
    tails[pos] = x
return tails.size

The trick: tails is always sorted (proof by induction); tails[k] is the smallest possible last value of any length-(k+1) increasing subsequence. The final length of tails is the LIS length — but tails itself is NOT a valid LIS.

2. Step-by-Step Analysis

Why the DP recurrence works The LIS ending at index i must come from some earlier index j with nums[j] < nums[i]. Extending that LIS by nums[i] gives a candidate length of dp[j] + 1.

Why dp[i] = 1 initially The subsequence consisting of nums[i] alone always has length 1.

Why patience sort works

tails[k] is the smallest possible tail of an LIS of length k+1. For each new x:
- If x > all tails, we can extend the LIS by one: append.
- Otherwise, replace the first tails[pos] >= x with x. This doesn’t change the answer length, but lowers the “tail” so future numbers can extend longer.

ASCII Trace for [10, 9, 2, 5, 3, 7, 101, 18]

DP:
i=0 nums=10  dp=1
i=1 nums=9   dp=1
i=2 nums=2   dp=1
i=3 nums=5   dp=2  (from i=2)
i=4 nums=3   dp=2  (from i=2)
i=5 nums=7   dp=3  (from i=3 or i=4)
i=6 nums=101 dp=4  (from i=5)
i=7 nums=18  dp=4  (from i=5)
max = 4

Patience:
x=10  tails=[10]
x=9   tails=[9]      (replace 10)
x=2   tails=[2]      (replace 9)
x=5   tails=[2,5]    (append)
x=3   tails=[2,3]    (replace 5)
x=7   tails=[2,3,7]
x=101 tails=[2,3,7,101]
x=18  tails=[2,3,7,18]   (replace 101)
length = 4

3. The Dry Run (Patience Sort)

Input: [10, 9, 2, 5, 3, 7, 101, 18]

Step	`x`	`tails` before	binarySearch returns	Action	`tails` after
1	10	[]	0 (= size)	append	[10]
2	9	[10]	0	replace tails[0]	[9]
3	2	[9]	0	replace tails[0]	[2]
4	5	[2]	1 (= size)	append	[2,5]
5	3	[2,5]	1	replace tails[1]	[2,3]
6	7	[2,3]	2 (= size)	append	[2,3,7]
7	101	[2,3,7]	3 (= size)	append	[2,3,7,101]
8	18	[2,3,7,101]	3	replace tails[3]	[2,3,7,18]

Return tails.size() == 4.

4. Java Solution

O(n²) DP

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int best = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }
}

O(n log n) — Patience Sort

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            int lo = 0, hi = size;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < x) lo = mid + 1; else hi = mid;
            }
            tails[lo] = x;
            if (lo == size) size++;
        }
        return size;
    }
}

5. The “Java vs. Others” Edge

Built-in Arrays.binarySearch returns a negative insertion point — usable but tricky; manual binary search is clearer for LIS.
>>> 1 (unsigned shift) avoids overflow on (lo + hi) / 2 for huge arrays.
For “actual LIS sequence” (not just length), patience sort needs back-pointers. DP version is simpler for reconstruction.

6. Complexity Summary

Approach	Time	Space	Notes
DP O(n²)	(O(n^2))	(O(n))	Simple, allows reconstruction
Patience Sort	(O(n \log n))	(O(n))	Length only without back-pointers