Section Recap

Look at what you can do now:

$1.$ Solve LIS with $O(n^2)$ DP using "ending at $i$" states

$2.$ Reduce to $O(n \log n)$ using binary search on tails array

$3.$ Count the number of LIS by tracking both length and count

$4.$ Reduce 2D (two-dimensional) problems to LIS (Russian Doll Envelopes) The "ending at $i$" pattern is your foundation for subsequence problems. Next, you'll extend to two sequences with LCS (Longest Common Subsequence) and Edit Distance.