109.Longest Increasing Subsequence

MediumBlind 751-D Dynamic Programming · 11/12

Problem

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

A subsequence keeps the original order but may skip elements: [3, 6, 2, 7] is a subsequence of [0, 3, 1, 6, 2, 2, 7]. "Strictly increasing" means each element is greater than the one before it — equal values do not count.

Examples

Input:  nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: [2, 3, 7, 101] (or [2, 5, 7, 18], etc.).

Input:  nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: [0, 1, 2, 3].

Input:  nums = [7, 7, 7, 7]
Output: 1
Explanation: Equal values are not strictly increasing.

Constraints

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4
Follow-up: can you do it in O(n log n)?

💡 Key Insight

Let dp[i] = length of the longest increasing subsequence ending at index i. It extends the best earlier subsequence whose last value is smaller: dp[i] = 1 + max(dp[j] for j < i with nums[j] < nums[i]) (or 1 if none), and the answer is max(dp) — O(n²). For O(n log n), keep tails[k] = the smallest possible tail value of any increasing subsequence of length k + 1. tails is always sorted, so each new number either extends the longest one or replaces the first tail >= it (found by binary search). The final size of tails is the answer.

Recursion (Brute Force)

TimeO(2ⁿ)SpaceO(n)

Intuition

Walk left to right, remembering the index prev of the last element we took. At index i, we can always skip nums[i]; we can take it only if it's larger than nums[prev]. Explore both choices.

Recurrence: f(i, prev) = max(f(i + 1, prev), 1 + f(i + 1, i) if prev == -1 or nums[i] > nums[prev]), with f(n, prev) = 0.

Algorithm

dfs(i, prev): if i == n return 0.
skip = dfs(i + 1, prev).
If prev == -1 or nums[i] > nums[prev]: take = 1 + dfs(i + 1, i).
Return max(skip, take); answer dfs(0, -1).

Visualization

nums = [1, 2, 4, 3]. The state (3, prev=1) — "at index 3, last taken was index 1" — is reached by two different paths.

flowchart TD
    A["f(0, -)"] -->|"take 1"| B["f(1, 0)"]
    A -->|"skip"| C["f(1, -)"]
    B -->|"take 2"| D["f(2, 1)"]
    B -->|"skip"| E["f(2, 0)"]
    D -->|"take 4"| F["f(3, 2)"]
    D -->|"skip"| G["f(3, 1)"]
    C -->|"take 2"| H["f(2, 1)"]
    H -->|"skip"| I["f(3, 1)"]
    G -->|"take 3"| J["f(4, 3) = 0"]

f(2, 1) and f(3, 1) each appear twice — the subtree below is recomputed.

Code

java

class Solution {
    public int lengthOfLIS(int[] nums) {
        return dfs(nums, 0, -1);
    }

    // longest increasing subsequence in nums[i..] given the last taken index prev
    private int dfs(int[] nums, int i, int prev) {
        if (i == nums.length) {
            return 0;
        }
        int skip = dfs(nums, i + 1, prev);
        int take = 0;
        if (prev == -1 || nums[i] > nums[prev]) {
            take = 1 + dfs(nums, i + 1, i);
        }
        return Math.max(skip, take);
    }
}

Complexity

Time: O(2ⁿ) — each element is taken or skipped.
Space: O(n) — recursion depth.

Top-Down Memoization

TimeO(n²)SpaceO(n²)

Intuition

The state is (i, prev), at most n × (n + 1) combinations. Cache them; shift prev by one so -1 maps to column 0.

Algorithm

memo[n][n + 1] filled with -1.
dfs(i, prev): return cached memo[i][prev + 1] if set, otherwise compute as in Approach 1 and store.

Dry Run

nums = [0, 1, 0, 3, 2, 3]
dfs(5, 4) = 1        take the final 3 after 2
dfs(4, 3) = 0        neither 2 nor 3 is > 3
dfs(4, 1) = 2        take 2, then 3
dfs(3, 1) = max(take 3 → 1 + dfs(4, 3) = 1,  skip → dfs(4, 1) = 2) = 2
dfs(0, -1) = 4       [0, 1, 2, 3]; every repeated (i, prev) is a cache hit

Code

java

import java.util.Arrays;

class Solution {
    private int[][] memo;

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        memo = new int[n][n + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(nums, 0, -1);
    }

    private int dfs(int[] nums, int i, int prev) {
        if (i == nums.length) {
            return 0;
        }
        if (memo[i][prev + 1] != -1) {
            return memo[i][prev + 1]; // column 0 stands for "nothing taken yet"
        }
        int skip = dfs(nums, i + 1, prev);
        int take = 0;
        if (prev == -1 || nums[i] > nums[prev]) {
            take = 1 + dfs(nums, i + 1, i);
        }
        memo[i][prev + 1] = Math.max(skip, take);
        return memo[i][prev + 1];
    }
}

Complexity

Time: O(n²) — n² states, O(1) each.
Space: O(n²) — the memo table (about 6.25 million ints for n = 2500, ~25 MB).

Bottom-Up Tabulation

TimeO(n²)SpaceO(n)

Intuition

Use the one-dimensional state instead: dp[i] = LIS ending exactly at i. Every earlier j with nums[j] < nums[i] can be extended by nums[i].

Recurrence: dp[i] = 1 + max(dp[j]) over j < i with nums[j] < nums[i]; dp[i] = 1 if no such j. Answer = max(dp[i]).

Algorithm

dp filled with 1.
For i = 1..n-1, for j = 0..i-1: if nums[j] < nums[i], dp[i] = max(dp[i], dp[j] + 1).
Return the maximum of dp.

Dry Run

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

i	0	1	2	3	4	5	6	7
nums[i]	10	9	2	5	3	7	101	18
dp[i]	1	1	1	2	2	3	4	4

dp[5] (value 7) extends dp[3] or dp[4] (both 2) → 3. dp[6] (101) extends dp[5] → 4. Answer 4.

Code

java

import java.util.Arrays;

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // each element alone is an increasing subsequence
        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); // append nums[i] after nums[j]
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }
}

Complexity

Time: O(n²) — double loop.
Space: O(n) — the dp array.

Patience Sorting + Binary SearchOptimal

TimeO(n log n)SpaceO(n)

Intuition

Among all increasing subsequences of a given length, the one with the smallest last value is the most useful — it is the easiest to extend. Maintain tails, where tails[k] is that smallest tail for length k + 1. tails is strictly increasing, so for each x:

If x is bigger than every tail, it extends the longest subsequence: append it.
Otherwise find the first tail >= x and replace it with x — a subsequence of the same length now ends lower.

tails is not itself an LIS, but its length always equals the LIS length.

Algorithm

tails = new int[n], size = 0.
For each x: binary-search the leftmost index lo in tails[0..size) with tails[lo] >= x.
tails[lo] = x; if lo == size, size++.
Return size.

Dry Run

flowchart TD
    A["x=10: tails=[10]"] --> B["x=9: replace 10 → [9]"]
    B --> C["x=2: replace 9 → [2]"]
    C --> D["x=5: append → [2,5]"]
    D --> E["x=3: replace 5 → [2,3]"]
    E --> F["x=7: append → [2,3,7]"]
    F --> G["x=101: append → [2,3,7,101]"]
    G --> H["x=18: replace 101 → [2,3,7,18]"]
    H --> I["size = 4"]

Code

java

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length]; // tails[k] = smallest tail of an LIS of length k+1
        int size = 0;
        for (int x : nums) {
            // leftmost position with tails[pos] >= x (lower bound)
            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;     // replace, or append when lo == size
            if (lo == size) {
                size++;
            }
        }
        return size;
    }
}

Complexity

Time: O(n log n) — one binary search per element.
Space: O(n) — the tails array.

Complexity Comparison

Approach	Time	Space
Recursion (Brute Force)	O(2ⁿ)	O(n)
Top-Down Memoization	O(n²)	O(n²)
Bottom-Up Tabulation	O(n²)	O(n)
Patience Sorting + Binary Search	O(n log n)	O(n)

Common Pitfalls

Returning dp[n - 1] instead of max(dp) — the LIS need not end at the last element.
Using <= in the comparison (or an upper-bound binary search), which counts equal values and breaks "strictly increasing" — [7, 7, 7] must give 1.
Assuming tails holds an actual LIS; it only has the right length. Reconstructing the sequence needs parent pointers.
Arrays.binarySearch returns an arbitrary match among duplicates and -(insertion point) - 1 otherwise; decode it carefully or write your own lower bound.