Dynamic Programming — Longest Increasing Subsequence

↗ LeetCode: Longest Increasing Subsequence · Medium · pattern chapter →

Asked atMetaAmazonGoogleMicrosoftLinkedIn

Return the length of the longest strictly increasing subsequence of nums.

Example 1 — nums=[10,9,2,5,3,7,101,18] → 4 (2,3,7,101) Example 2 — nums=[0,1,0,3,2,3] → 4Example 3 — nums=[7,7,7,7,7] → 1

Constraints — 1 ≤ n ≤ 2500; -10⁴ ≤ nums[i] ≤ 10⁴. Brute enumerates all 2ⁿ subsequences — 2·10³ length = 10⁶⁰²⁰ ops (dead). DP is O(n²) = 4·10⁶ ops = ~20 ms; binary-search patience sort is O(n log n) = 2·10⁴ ops.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Brute force recursion

Intuition. For each i, either include or exclude — 2^n subsets.

Complexity — Time O(2ⁿ); Space O(n). Useless past n≈20.

Approach 2 — DP (O(n²))

Insight. dp[i] = longest increasing subsequence ending at i. Recurrence: dp[i] = 1 + max(dp[j] : j < i and nums[j] < nums[i]).

java

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

Complexity — Time O(n²); Space O(n).

Approach 3 — Patience sort with binary search (O(n log n))

Insight from DP. Maintain tails[] where tails[k] = smallest tail value of any LIS of length k+1. tails stays sorted → for each new x, binary search for the first tails[k] >= x and overwrite it. Final LIS length = tails.length.

tails is not an actual LIS — just their length-indexed minima. But its length equals the answer.

java

int lengthOfLIS(int[] a) {
    int[] tails = new int[a.length];
    int len = 0;
    for (int x : a) {
        int i = Arrays.binarySearch(tails, 0, len, x);
        if (i < 0) i = -(i + 1);
        tails[i] = x;
        if (i == len) len++;
    }
    return len;
}

Execution Trace

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

Step 1 / 7seed

Complexity — Time O(n log n); Space O(n).

Try it yourself

Complexity summary

Approach	Time	Space
Brute enumerate subsets	O(2ⁿ)	O(n)
O(n²) DP	O(n²)	O(n)
Patience sort + BS	O(n log n)	O(n)

When to use which

Just the length → patience sort.
Need to reconstruct the subsequence → O(n²) DP with prev[i] traceback.
Non-strict (≤) → binary search for first > x instead of >= x.

✨AI Study CompanionBeta

Longest Common Subsequence — 2D DP
Longest Palindromic Subsequence — LCS(s, reverse(s))
Russian Doll Envelopes — sort by width, LIS on heights
Number of Longest Increasing Subsequence — track count alongside length

Was this page helpful?

📚 Related problems

Dynamic Programming — Longest Increasing Subsequence ​

Approach 1 — Brute force recursion ​

Approach 2 — DP (O(n²)) ​

Approach 3 — Patience sort with binary search (O(n log n)) ​

Try it yourself ​

Complexity summary ​

When to use which ​

Related problems ​