Longest Increasing Subsequence

Explanation & Solution

Description

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

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Input:nums = [10,9,2,5,3,7,101,18]

101

Output: 4

Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Constraints

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

Approach

Dynamic Programming pattern

1. Define the DP Array

Create an array dp of the same length as nums, initialized to 1
dp[i] represents the length of the longest increasing subsequence that ends at index i
Every element by itself is a subsequence of length 1, hence the initialization to 1

2. Build Up the DP Table

For each index i from 1 to nums.length - 1:
Look at every previous index j from 0 to i - 1
If nums[j] < nums[i], then nums[i] can extend the subsequence ending at j
Update dp[i] = max(dp[i], dp[j] + 1)

3. Find the Maximum

The answer is the maximum value in the entire dp array
The longest increasing subsequence could end at any index, not necessarily the last one

4. Why This Works

By checking all previous elements for each position, we consider every possible subsequence
The DP recurrence ensures that we always extend the longest possible subsequence ending before the current element
The strictly increasing condition is enforced by the nums[j] < nums[i] check

Key Insight

This is a classic DP problem where each state depends on all previous states, not just the immediately preceding one
The O(n * log n) patience sorting approach exists, but the O(n^2) DP solution is more intuitive and easier to implement

Time

O(n^2) where n is the length of the array

Space

O(n) for the DP array

Visualization

Input:

Dynamic Programmingnums = [10,9,2,5,3,7,101,18]

Press play to start DP animation

ComputingDependencyFilledEmpty

9 steps

Solution Code

Coin Change II

Word Break