Loading problem…
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of [0,3,1,6,2,2,7].
Example 1
Input: nums = [3,5,6,2,5,4,19,5,6,7,12]
Output: 6
Explanation: One longest increasing subsequence is 3, 4, 5, 6, 7, 12 (skipping 5, 6, 2, 19 and so on). It has 6 elements, and no longer one exists.
Example 2
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: One longest increasing subsequence is [2,3,7,101] (or [2,5,7,18]). It has 4 elements.
Example 3
Input: nums = [0,1,0,3,2,3]
Output: 4
Explanation: The subsequence [0,1,2,3] is strictly increasing and has 4 elements.
Maintain `tails[k]` = the **smallest possible tail** of any increasing subsequence of length `k+1`. For each `x`, binary-search the position where `x` would go: if it extends `tails`, append; else replace to keep tails minimal. The final length of `tails` is the LIS length. > `tails` is *not* the actual subsequence — it's a compact bookkeeping of what > tails are achievable.
Run checks all cases above. Submit evaluates all test cases.