Problem. Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence
keeps the original order but may skip elements.
nums = [10, 9, 2, 5, 3, 7, 101, 18] → 4 (2, 3, 7, 18 or 2, 5, 7, 101)
nums = [7, 7, 7, 7] → 1
Unlike a subarray, a subsequence can skip, so there are 2ⁿ of them. The DP state that makes it tractable is "the longest increasing subsequence ending at position i": whatever came before i in that subsequence ended at some smaller value earlier.
ML context. Monotone structure in noisy sequences: the longest run of checkpoints whose validation score kept improving (Change D) shows how often training made real progress; aligning two orderings (how much of a predicted ranking agrees with the true one) reduces to an increasing subsequence; and the O(n log n) "smallest tail per length" trick is a compact example of maintaining a sorted summary with binary search (module 05).