Longest Increasing Subsequence

Difficulty: Hard

Problem

Given an integer array, return the length of its longest STRICTLY increasing subsequence: values picked from left to right (order kept, gaps allowed) where each pick is bigger than the one before. The classic that teaches DP's most subtle state definition.

Example

Input: nums = [3,10,2,1,20]
Output: 3
Explanation: One longest increasing subsequence is [3, 10, 20], length 3. No increasing pick of 4 elements exists.

Brute-force approach

Enumerating all 2ⁿ subsequences is hopeless. The guided walkthrough shows why and builds the O(n²) DP directly.

Optimal approach

Key insight: Pin the state to 'chains ENDING at i' and the impossible question 'what's the best subsequence?' becomes a checkable one: 'which smaller earlier ending can I extend?'

For each index i, dp[i] = 1 + the best dp[j] over earlier smaller values. The answer is the maximum over all endings.

Steps

  1. State: dp[i] = length of the longest increasing chain ending exactly at i
  2. Every dp[i] starts at 1 (the element alone)
  3. For each j < i with nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1)
  4. Answer: max over the whole dp array

Time complexity: O(n²) · Space complexity: O(n)

Pseudocode

function lengthOfLIS(nums):
    dp = array of length(nums), filled with ____
    
    for i in 0 .. length(nums)-1:
        for j in 0 .. i-1:
            if nums[j] ____ nums[i]:
                dp[i] = max(dp[i], dp[j] + ____)
    
    return ____(dp)

Hints

  • Every element alone is already a chain, of what length?
  • nums[i] can only extend chains ending in STRICTLY smaller values, which comparison?
  • Extending a chain adds exactly this element to it
  • Chains end anywhere: which aggregate over dp gives the answer?

Complexity questions

Why is this DP O(n²) rather than O(n)?

The transition's reach isn't constant: each dp[i] may scan ALL earlier indexes, not just the last two. Stairs/robber reached back a fixed 2 slots. Here the second-to-last element can be ANY earlier smaller value: an O(i) scan per index sums to O(n²).

Can this table roll down to O(1) like the earlier problems?

No: the transition reads arbitrarily far back, so the whole O(n) table must stay alive. Rolling variables require a bounded reach. dp[i] may need dp[0], every entry stays relevant forever. The reach audit says: keep the table.

A solution returns dp[len(nums)−1] instead of max(dp). What happens?

Right whenever the best chain happens to end at the last element, silently wrong otherwise, e.g. [1,5,2] answers 2's chain (2) instead of 2 (the chain 1,5)... it returns dp[last] = 2 which is right there; but [3,4,1] returns 1 instead of 2. On [3,4,1] the best chain (3,4) ends mid-array: max(dp) = 2 but dp[last] = 1. Tests with ascending tails pass; others fail, the classic intermittent bug.

The O(n log n) LIS keeps an array of 'smallest tail per chain length' and binary-searches it. Why mention it here?

To plant the flag: the O(n²) DP is the expected first answer; the patience-sorting upgrade is a follow-up worth knowing EXISTS, learned after the DP is solid. Interviewers want the DP reasoning first. 'And with patience sorting this drops to O(n log n)' is the excellence marker. Pursue it once this version is reflex.

Check your understanding of Longest Increasing Subsequence

What is a subsequence (versus a subarray)?

Elements in their original order, but you may SKIP any you like. Subarrays are contiguous; subsequences keep order but may skip. In [10,9,2,5,3,7...], the picks 2 → 3 → 7 skip over 5, perfectly legal for a subsequence.

Why is the state 'dp[i] = LIS length ENDING exactly at index i', why the 'ending at' part?

Because to extend a chain with nums[i], you must know the chain's LAST value is smaller, 'ending at j' pins that last value to nums[j], making the check possible. 'LIS of the first i elements' doesn't tell you what that LIS ENDS with, so you can't know whether nums[i] may extend it. Pinning the ending makes the transition checkable: nums[j] < nums[i] means chain-ending-at-j extends to i.

The transition for dp[i]?

dp[i] = 1 + max(dp[j]) over all j < i with nums[j] < nums[i], or just 1 if no such j exists. The chain ending at i has a second-to-last element: some earlier, SMALLER nums[j]. Try them all, take the longest such chain, add nums[i]. No candidate? nums[i] starts a fresh chain of length 1.

Where does the final answer live?

max over the WHOLE dp array. The best chain can end anywhere. The classic trap! In [10,9,2,5,3,7], the best chain ends at 7 (index 5), but in [1,5,2], it ends mid-array at 5. 'Ends anywhere' means max(dp), not dp[last].

Trace [10,9,2,5,3,7]: what is dp[5] (the 7)?

3: extend the length-2 chain ending at 5 or at 3. Smaller earlier values: 2 (dp=1), 5 (dp=2), 3 (dp=2). Best is 2, so dp[5] = 3, e.g. the chain 2, 5, 7 or 2, 3, 7.

Keep practising