BinarySearch 0050 Longest Increasing Subsequence

Problem statement

https://binarysearch.com/problems/Longest-Increasing-Subsequence/

Solution

Equal to leetcode 300. Longest Increasing Subsequence.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        dp = [10**10] * (len(nums) + 1)
        for elem in nums: dp[bisect_left(dp, elem)] = elem  
        return dp.index(10**10)