Longest Increasing Subsequence

Return the length of the longest strictly increasing subsequence of nums (a subsequence keeps the order but may skip values).

For [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4 (2, 3, 7, 18).

The starter code compares every value with all earlier ones. It is correct but too slow for long lists.

Examples

Example 1

Input:

length_of_lis([10, 9, 2, 5, 3, 7, 101, 18])

Output:

4

Example 2

Input:

length_of_lis([7, 7, 7, 7])

Output:

1

Constraints

• 0 <= len(nums) <= 200000
• -10**9 <= nums[i] <= 10**9