LeetCode 300 Longest Increasing Subsequence - Walkthrough

Trace LIS on $[10, 9, 2, 5, 3, 7, 101, 18]$. Let $dp[i]$ = length of LIS ending at $i$. $dp[0] = 1$ (just $10$). $dp[1] = 1$ (just $9$, can't extend from $10$). $dp[2] = 1$ (just $2$). $dp[3] = 2$ (extend from $2$: $[2, 5]$). $dp[4] = 2$ (extend from $2$: $[2, 3]$). $dp[5] = 3$ (extend from $5$ or $3$: $[2, 5, 7]$). $dp[6] = 4$ (extend from $7$: $[2, 5, 7, 101]$). $dp[7] = 4$ (extend from $7$: $[2, 5, 7, 18]$).

Answer: $\max(dp) = 4$.