Longest Increasing Subsequence: DP and Patience

Longest Increasing Subsequence is the gateway DP problem and the gateway patience-sorting problem in one prompt. There are two solutions worth knowing, and they teach different lessons. The O(n^2) DP teaches you to articulate a recurrence. The O(n log n) version teaches you to spot a classical algorithm hiding under a different name.

The Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps relative order but does not need to be contiguous.

Intuition

For the DP, define dp[i] as the length of the longest increasing subsequence ending exactly at index i. Any such subsequence extends a shorter one ending at some earlier index j with nums[j] < nums[i], so dp[i] = 1 + max(dp[j]) over all such j, with default 1.

For the upgrade, observe that we don’t need to remember every subsequence — only the smallest possible tail value for each length seen so far. A new value x either extends the longest-known length by one (when x exceeds every tail) or replaces the first tail that is greater-or-equal (improving the tail for that length). Binary search makes this O(log n) per element.

Explanation with Example

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

Patience version step by step:

• 10 -> tails [10].
• 9 -> replace 10. Tails [9].
• 2 -> replace 9. Tails [2].
• 5 -> append. Tails [2, 5].
• 3 -> replace 5. Tails [2, 3].
• 7 -> append. Tails [2, 3, 7].
• 101 -> append. Tails [2, 3, 7, 101].
• 18 -> replace 101. Tails [2, 3, 7, 18].

Answer: 4. One witnessing LIS is [2, 3, 7, 18] or [2, 3, 7, 101] — note that the final tails array happens to be a valid LIS here, but in general it need not be.

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

dp[i] = 1 + max(dp[j]) over j<i where nums[j] < nums[i]
dp[5] (=3): from dp[3]=2 via 5<7  -> 3
dp[6] (=4): from dp[5]=3 via 7<101 -> 4

num    tails after step
10     [10]
9     [9]
2     [2]
5     [2,5]
3     [2,3]
7     [2,3,7]
101    [2,3,7,101]
18    [2,3,7,18]   length = 4

Code

Two solutions: the O(n^2) DP for clarity, and the O(n log n) patience-sorting version using binary search. The tails contents are not an actual increasing subsequence — only the length is meaningful.

# O(n^2) DP
def lengthOfLIS_dp(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)


# O(n log n) patience sorting
from bisect import bisect_left

def lengthOfLIS(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

import java.util.*;

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int x : nums) {
            int i = Collections.binarySearch(tails, x);
            if (i < 0) i = -(i + 1);
            if (i == tails.size()) {
                tails.add(x);
            } else {
                tails.set(i, x);
            }
        }
        return tails.size();
    }
}

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int x : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), x);
            if (it == tails.end()) {
                tails.push_back(x);
            } else {
                *it = x;
            }
        }
        return (int)tails.size();
    }
};

Edge Cases

• Empty array — return 0.
• Strictly decreasing input — the answer is 1; tails has length 1 throughout.
• All equal values — strictly increasing rules out duplicates, so the answer is 1.
• Single element — answer is 1.
• Non-strict variants — use bisect_right (or upper_bound) instead of bisect_left to allow equal values.

Complexity Analysis

The O(n^2) DP costs O(n^2) time and O(n) space. The patience version costs O(n log n) time and O(n) space.

For inputs up to a few thousand the DP is fine and easier to defend. Past that, patience wins outright.

How to Explain It in an Interview

Open with the DP definition: “dp[i] is the length of the longest increasing subsequence ending at index i.” Derive the recurrence and the time bound. Then volunteer the upgrade: “I can do this in n log n by maintaining the smallest possible tail of any increasing subsequence of each length. Each new number either extends the tails array or replaces the first tail it could fit under.”

If the interviewer asks “is tails the LIS?” — clearly say no, and explain that you would have to reconstruct using parent pointers stored alongside.

If they ask to reconstruct the LIS, fall back to the DP version with a prev[i] array — it is the path of least surprise.

Related Problems

• Russian Doll Envelopes (LIS after a clever sort)
• Number of Longest Increasing Subsequences
• Minimum Removals to Make Mountain Array
• Maximum Length of Pair Chain

Each builds on LIS by adding a wrapper — sorting, counting, or pairing. The classic LIS engine sits at the core.

Related practice

LIS is the headline example of a one-dimensional DP that admits an algorithmic upgrade. If you want more DP scaffolding before tackling it, the Classic DP Problems post walks through several smaller examples.

Wrap up

LIS is the rare problem where the O(n log n) version is short enough that interviewers expect it. Burn the patience-sorting code into muscle memory and explain why the tails array is a length-witness rather than an actual subsequence. Once you can articulate both solutions and their trade-offs in 90 seconds, LIS goes from a feared question to a routine win.