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]`

. 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.

(Image credit: DALLĀ·E 3)

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