import bisect
class Solution:
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = []
        for n in nums:
            pos = bisect.bisect_left(dp, n)
            if pos == len(dp):
                dp.append(n)
            else:
                dp[pos] = n
        return len(dp)