Lessons from LIS

Three patterns to remember from LIS (Longest Increasing Subsequence):

$1.$ "Ending at $i$" states let you know exactly what to extend from. This pattern appears in many subsequence problems.

$2.$ The answer might not be at the last index. Check if you need $\max(dp)$ or $dp[n-1]$.

$3.$ Picking the locally best option fails when those choices affect future options. DP (dynamic programming) explores all paths. The $O(n^2)$ solution works for $n \le 2500$. For larger inputs, you need the $O(n \log n)$ improvement.