单调递增最大子序列代码

以下是使用动态规划的单调递增最大子序列的代码：

def longest_increasing_subsequence(nums):
    if not nums:
        return 0
    
    # dp[i]表示以nums[i]结尾的最长递增子序列的长度
    dp = [1] * len(nums)
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

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

可以通过使用二分查找优化到$O(nlogn)$的时间复杂度，以下是优化后的代码：

def longest_increasing_subsequence(nums):
    if not nums:
        return 0
    
    # tails[i]表示长度为i+1的递增子序列的最后一个元素的最小值
    tails = [nums[0]]
    
    for num in nums[1:]:
        if num > tails[-1]:
            tails.append(num)
        else:
            left, right = 0, len(tails) - 1
            while left < right:
                mid = (left + right) // 2
                if tails[mid] < num:
                    left = mid + 1
                else:
                    right = mid
            tails[left] = num
    
    return len(tails)

时间复杂度：$O(nlogn)$