Dynamic Programming — Longest Increasing Subsequence

Return the length of the longest strictly increasing subsequence of
nums. A subsequence keeps the original order but may skip elements:
[2, 3, 7, 18] is one in [10, 9, 2, 5, 3, 7, 101, 18].

The textbook DP, "LIS ending at i = 1 + best LIS ending at an earlier smaller
value", is O(n²). The follow-up interviewers ask for is O(n log n): keep
tails[k], the smallest possible last value of an increasing subsequence of
length k + 1. tails stays sorted, so each new number finds its place by
binary search, replacing the first tail >= it or extending the array.

Examples

solve([10, 9, 2, 5, 3, 7, 101, 18])  → 4
solve([0, 1, 0, 3, 2, 3])            → 4
solve([7, 7, 7, 7])                  → 1   // strictly increasing

Constraints

• 0 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4