Given an integer array nums, return the length of its longest strictly increasing subsequence. A subsequence keeps order but may skip elements: [2,5,7] is a subsequence of [2,1,5,3,7]. Strictly increasing — equal neighbours do not count.
Examples
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: [2,3,7,101] (or [2,5,7,101]).
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7]
Output: 1
Example 4:
Input: nums = [4,10,4,3,8,9]
Output: 3
Constraints
1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4
Prerequisites
Dynamic programming — being able to say, in one sentence, what a single cell of your table MEANS. Everything else follows from that sentence. Rolling variables: when a state only looks back one or two steps, the table collapses to a couple of numbers.
How to think about it
1. Longest Ending Here Optimal
Intuition
best[i] means "the longest increasing subsequence that ENDS at i" — anchoring the definition at an endpoint is what makes the recurrence work, because any such subsequence is some shorter one ending at a smaller earlier value, extended by i. The answer is the largest of those, not the last.
Algorithm
1. Every position starts at length 1: itself. 2. For each i, look back over every earlier j with a strictly smaller value. 3. Take the best of those and add one. 4. Answer with the largest value in the table.
Time & Space
Time O(n^2). Space O(n). The O(n log n) follow-up keeps the smallest possible tail for each length and binary-searches where each value lands.