Longest Increasing Subsequence

A subsequence keeps some items of a list in their original order, possibly skipping others. Write lis_length(nums) that returns the length of the longest subsequence of nums in which every number is strictly bigger than the one before it.

Examples

lis_length([3, 1, 4, 1, 5, 9, 2, 6])  # returns 4
lis_length([2, 8, 3, 9, 4, 10, 5])    # returns 4
lis_length([5, 5, 5])                 # returns 1
lis_length([])                        # returns 0

In the first list, 1, 4, 5, 9 is one longest increasing subsequence and 3, 4, 5, 6 is another.

Constraints

• 0 <= len(nums) <= 1000
• -10**6 <= nums[i] <= 10**6

Note

Comparing every pair of positions is fast enough for these sizes. Once that works, there is a quicker method that runs in O(n log n): worth discovering.