原题出处：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xwhvq3/

解法一：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        d = []
        for i in range(n):
            if not d or nums[i] > d[-1]:
                d.append(nums[i])
            else:
                l, r = 0, len(d) - 1
                while (l < r):
                    mid = (l + r) // 2
                    if (d[mid] < nums[i]):
                        l = mid + 1
                    else:
                        r = mid
                d[l] = nums[i]
        return len(d)

思路：二分查找法，定义一个数组用来保存最大子序数组d，遍历数组 nums，对于每个元素 nums[i]，我们在 d 数组中查找第一个大于等于 nums[i] 的元素 d[j]，然后更新 d[j] 的值为 nums[i]。如果不存在这样的元素 d[j]，则说明 nums[i] 大于 d 数组中的所有元素，此时我们将 nums[i] 添加到 d 数组的末尾。