210. Longest Increasing Subsequence

Define dp[i] = length of the longest increasing subsequence that ends at index i. Why end-at? Because then any valid subsequence ending at i must extend some shorter subsequence ending at some earlier index j where nums[j] < nums[i]. The recurrence falls out: dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]), with 1 as the default if no such j exists.

Why "ending at i" is the right state

If we instead defined dp[i] as "length of LIS in nums[0..i]", we'd lose track of which element ended the subsequence — and that matters when extending to i+1. Anchoring on "the subsequence ends here" makes the transition local: we only need dp[j] for earlier j whose value is smaller.

Steps

1. If nums is empty, return 0.
2. Initialise dp = [1] * n — every index, by itself, is a length-1 increasing subsequence.
3. For each i from 1 to n - 1:
   • For each j from 0 to i - 1:
     • If nums[j] < nums[i], set dp[i] = max(dp[i], dp[j] + 1).
4. Return max(dp) — the answer can end at any index, so we take the global max.

Walk-through

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

max(dp) = 4. ✓

The actual LIS realising length 4: [2, 3, 7, 101] or [2, 3, 7, 18] etc.

Edge cases

• Empty list: return 0.
• Single element: dp = [1], return 1.
• All decreasing: every dp[i] = 1, answer is 1.

Complexity

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

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        java.util.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;
    }
}

Maintain tails[k] = the smallest possible tail of any increasing subsequence of length k+1. For each x, binary-search the position where x would go: if it extends tails, append; else replace to keep tails minimal. The final length of tails is the LIS length.

tails is not the actual subsequence — it's a compact bookkeeping of what tails are achievable.

Walk-through

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

Length 4.