Longest Increasing Subsequence

time O(n^2)space O(n)

The key insight: any increasing subsequence ending at index i must have come from some earlier, smaller element — so the longest one ending at i is just 1 more than the best chain among all valid predecessors. dp[i] stores that length for the subsequence ending exactly at index i; filling it in means scanning every earlier index j and, whenever nums[j] is smaller, checking whether extending that chain beats what dp[i] already holds. Because every dp[j] for j < i is already known by the time you reach i, this one pass builds up the full table, and the answer is simply the largest value dp ever holds.

Details

Animated on: nums=[10,9,2,5,3,7,101,18], O(n^2) dp: dp[i] = length of LIS ending at index i

Problem:Longest Increasing SubsequenceMedium

Pattern:1D Dynamic Programming

Dynamic Programming

step 1 / 8

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Initialize dp[i] = 1 for all i, each element alone is a subsequence of length 1

Pseudocode

1FUNCTION lengthLIS(nums):
2  n = the length of nums
3  dp = a list of n ones (dp[i] = LIS length ending at i)
4  FOR i from 1 to n-1:
5    FOR j from 0 to i-1:
6      IF nums[j] < nums[i]:
7        dp[i] = the larger of dp[i] and dp[j] + 1
8  RETURN the largest value in dp

← / → step · space play · Home restart

Every step in words

Show all 8 steps

Initialize dp[i] = 1 for all i, each element alone is a subsequence of length 1
i=1: nums[1]=9, check j=0: nums[0]=10 > 9, no valid previous, dp[1] stays 1
i=2: nums[2]=2, check j=0: 10>2, j=1: 9>2, no valid previous, dp[2] stays 1
i=3: nums[3]=5, check j=2: nums[2]=2<5, dp[3]=max(1, dp[2]+1=2)=2, LIS [2,5]
i=4: nums[4]=3, check j=2: nums[2]=2<3, dp[4]=max(1, dp[2]+1=2)=2, LIS [2,3]
i=5: nums[5]=7, check j=3: nums[3]=5<7, dp[5]=max(1, dp[3]+1=3)=3, LIS [2,5,7]; also j=4: nums[4]=3<7, dp[5]=max(3, dp[4]+1=3)=3, LIS [2,3,7]
i=6: nums[6]=101, check j=5: nums[5]=7<101, dp[6]=max(1, dp[5]+1=4)=4, LIS [2,3,7,101]
Answer: max(dp) = 4, LIS is [2,3,7,101] or [2,3,7,18] or [2,5,7,101] etc — length 4

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest Increasing Subsequence in the editor All Dynamic Programming problems Back to roadmap