Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence keeps some of the elements, in their original order, and drops the rest. They don't have to be next to each other. "Strictly increasing" means each kept element is larger than the one before it, so two equal values can't both be in it.
1, 2, 5, 9 is one longest choice. Starting from 3 gets no further than 3, 8, 9 or 3, 5, 9.
Equal values don't count as increasing, so only one 6 can be used.
-5, -2, 0, 3, 10 skips the 4 and the 7.
Constraints
1 <= nums.length <= 2500-10⁴ <= nums[i] <= 10⁴For each position, ask how long an increasing subsequence can be if it ends exactly there. It extends the best one that ends at some earlier, smaller value, or starts fresh at length 1.
A subsequence can skip anything, so the number of choices explodes: every element is either kept or dropped, which is 2ⁿ subsequences. At n = 2500 you can't look at them all. You need to build long subsequences out of shorter ones.
Time O(n log n)Space O(n)
The full walkthrough and code are part of Premium
4