LeetCode 300: Longest Increasing Subsequence

Last week, we looked at a problem involving a subarray. A subarray is a contiguous sequence of elements from an array, meaning we can’t skip any elements when building the answer. A subsequence, on the other hand, allows us to skip elements, though the elements in the subsequence still need to stay in their original order.

LeetCode 300: Longest Increasing Subsequence says:

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

So we’re allowed to skip elements, but we can’t change the order of the elements, and for this problem, the elements in the solution must be strictly increasing.

Nested Loops

As we did last week, let’s consider an array dp of the same size as the input array. dp[i] will store the length of the longest increasing subsequence that ends at element nums[i]. Since this problem uses a subsequence, not a subarray, dp[i] must include element nums[i]. As a base case, we can initialize dp with 1, since every element can at least make a subsequence of length 1. (The problem considers a sequence of length 1 to meet the definition of “strictly increasing”).

Now we need a state transition rule for dp[i]. If we construct dp in bottom-up order, then dp[i-1] will always contain the length of the LIS ending at i-1. So if nums[i] > nums[i-1], we can add nums[i] to the end of the subsequence, giving us a subsequence length of dp[i-1] + 1.

But because we’re analyzing a subsequence, not a subarray, we can’t guarantee an optimal solution if we only compare nums[i] with nums[i-1]. For example, consider the input [1, 3, 2, 3, 1]. If we only compare adjacent elements, we’ll only find increasing subsequences of length 2: [1, 3] and [2, 3]. By looking at the entire input, we can find the optimal subsequence, [1, 2, 3].

One way to ensure that we append the current element to the best subsequence is to check every input value up to the current element. So rather than just looking at nums[i-1], we should look at every element from nums[0] to nums[i-1] and find the one that gives us the longest strictly increasing subsequence.

Here’s how that looks in pseudocode, using two nested loops:

n = nums.Length
dp = int array of size n, with all elements initialized to 1

maxLen = 1
for i from 1 to n-1
    for j from 0 to i-1
        if nums[i] > nums[j]
            dp[i] = max(dp[i], dp[j] + 1)

    maxLen = max(maxLen, dp[i])

return maxLen

Coin Change also uses two nested loops (or a loop inside a recursive function, in the top-down implementation). But in Coin Change, we iterate over the set of coins. For this problem, both loops iterate over the input array.

Patience Solitaire

Since both loops in the nested loop solution to Longest Increasing Subsequence depend on n, we have an $O(n^2)$ time solution. There is also a way to solve this problem in $O(n \log n)$ time using binary search. You can find the details here:

• The Patience Solitaire method from Princeton CS has some good diagrams showing how to solve the problem as a card game.

• archit91 on LeetCode has explanations and code for several solutions, including dynamic programming and binary search methods.

Thanks to Daniel Zingaro for suggesting an improvement to this article.

(Image credit: DALL·E 3)

For an introduction to this year’s project, see A Project for 2024.