Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Problem

Longest Increasing Subsequence

LeetCode #300Medium

dp[i] = longest increasing run ENDING at i

Given an integer array, return the length of its longest strictly increasing subsequence (elements need not be contiguous but must keep their original order).

Asked atAmazonMicrosoftGoogle

DP on ending index (O(n²))

time O(n²)space O(n)

step 1 / 17

101

[0][1][2][3][4][5][6][7]

DP on ending index (O(n²))


▸
1n = len(nums)
2dp = [1] * n                       // each element alone
3for i in 0..n−1:
4    for j in 0..i−1:
5        if nums[j] < nums[i]:      // smaller predecessor
6            dp[i] = max(dp[i], 1 + dp[j])
7return max(dp)

state

nums[10, 9, 2, 5, 3, 7, 101, 18]
recurrencedp[i] = 1 + max(dp[j] | j<i, nums[j]<nums[i])

line 1Longest Increasing Subsequence: from nums, pick a subsequence (keep order, may skip) whose values strictly increase, and make it as long as possible. The DP idea: define dp[i] = length of the longest increasing subsequence that ENDS exactly at index i. Anchoring every subsequence at its last element turns one hard question into n small ones.