Longest Increasing Subsequence

February 11, 2021

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Key Intuition

To build the recurrence relation, we could ask ourselves whether the answer for $n - 1$ elements help us solve the entire sequence.

Suppose we know the longest increasing sequence in $(S_0, S_1, ..., S_{n-1})$ is of length $5$, and that $S_n = 8$. Will the longest increasing subsequence of $S$ be $5$ or $6$? It depends on whether the length-$5$ sequence ends with a value less than $8$.

Therefore, we really need to check every number $(S_0, S_1,...S_j)$ where $j < n$ and see whether $S_n > S_j$.

Code

public int lengthOfLIS(int[] nums) {
int result = 1;
int dp[] = new int[nums.length];
Arrays.fill(dp, 1);

for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
result = Math.max(dp[i], result);
}

return result;
}