最长递增子序列

Table of Contents

LIS最长递增子序列 - This article is part of a series.

Part : This Article

O(n^2)方法 #

对于第i个元素, 我们可以遍历其前面的所有数, 然后找到比nums[i]小的数nums[j], 然后比较把nums[i]放在nums[j]之后的序列会不会更长一点.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:

        @cache
        def dfs(i):
            res = 0
            for j in range(i): # 遍历比nums[i]小的数
                if nums[j] < nums[i]:
                    res = max(res, dfs(j)) # 判断能不能更长
            return res + 1
        

        return max(dfs(i) for i in range(len(nums)))

O(nlogn) 方法 #

在上一个方法中, 需要遍历所有i之前且比nums[i]小的数. 如果能快速找到这些数,那么就能提高算法效率.

因此, 如果我们把每个长度的子序列的末尾值都记录成一个数组g. 那么数组g一定是单调增加的. 例如如果g现在是 [1, 3, 7], 那么说明长度为1的递增子序列中, 最后那个数最小是1. 长度为2的递增子序列中,最后那个数最小值是3… 如果现在遍历到的nums[i]是5, 通过二分查找可以知道5应该在3的后面, 说明可以在长度为2的递增子序列后面再增加一个5. 那么长度为3的递增子序列的最后一个数的最小值就是5. 在g数组中进行替换即可.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        N = len(nums)
        g = []
        for i in range(N):
            j = bisect_left(g, nums[i])
            if j == len(g):
                g.append(nums[i])
            else:
                g[j] = nums[i]
        
        return len(g)

LIS最长递增子序列 - This article is part of a series.

Part : 俄罗斯套娃信封问题

Part : This Article