Longest Increasing Subsequence

LeetCode 300 • Medium • Dynamic Programming

Input: nums = [10,9,2,5,3,7,101,18] → Output: 4. dp[i] = LIS ending at i. dp[i] = 1 + max(dp[j]) for j<i where nums[j]<nums[i].

TimeO(n²)

SpaceO(n)

i: — j: — max: —

i (current)

j (compare)

dp[i]

i —

j —

dp [ ]

Speed:

Ready

Press Play. For each i, check all j<i: if nums[j]<nums[i], dp[i]=max(dp[i], dp[j]+1).

Whiteboard

Size:3

Type It

Practice until you don't need to look. dp[i] = LIS ending at i.

═══ LONGEST INCREASING SUBSEQUENCE — DP ═══

PATTERN ▸ DP (LIS ending at i) O(n²) · O(n)

① INIT

dp = [1]*n

② NESTED LOOP

for i: for j<i:

if nums[j]<nums[i]: dp[i]=max(dp[i], dp[j]+1)

③ RETURN

return max(dp)

your implementation

Verify: