Return the length of the longest strictly increasing subsequence (not necessarily contiguous).
Two solutions: the intuitive O(n²) DP, and the clever O(n log n) patience-sort with binary search.
O(n²) DP: dp[i] = longest LIS ending at i = 1 + max(dp[j]) for j<i with nums[j]<nums[i]. The optimal O(n log n): maintain `tails`, where tails[k] is the smallest possible tail of an increasing subsequence of length k+1; binary-search each number's slot and replace/append. Length of tails is the answer. Mention both; code the elegant one. The trick to internalize: `tails` is not itself a valid subsequence — it's a set of best-case endings, kept sorted precisely so binary search is legal. Replacing an existing tail with a smaller value leaves more room for future extensions without changing the current best length. Use lower-bound (first tail ≥ x) for strictly-increasing; switch to upper-bound if the problem allows equal values (non-decreasing).
Subsequence optimization; and when an O(n²) DP has a monotonic structure you can binary-search → patience sorting.
Time O(n log n) · Space O(n)