力扣 300. 最长递增子序列

时间复杂度$O(n^2)$

def lengthOfLIS(nums):
    #  动态规划
    dp = [1 for _ in range(len(nums))]
    ret = 1
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[j] + 1, dp[i])
        ret = max(ret, dp[i])
    return ret

时间复杂度$O(nlogn)$

def lengthOfLIS(nums):
    #  动态规划 + 二分查找
    dp = [0 for _ in range(len(nums))]
    ret = 0
    for num in nums:
        i, j = 0, ret
        while i < j:
            m = i + j >> 1
            if dp[m] < num:
                i = m + 1
            else:
                j = m
        dp[i] = num
        if i == ret: ret += 1

    return ret