300. 最长上升子序列

一、300. 最长上升子序列 1.1、题目描述

1.2.1、粗暴法（超时）

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        return self.recursive(nums, float('-inf'), 0)

    def recursive(self, nums: List[int], preV: int, curPos: int) -> int:
        if curPos == len(nums):
            return 0

        token = 0
        if nums[curPos] > preV:
            token = 1 + self.recursive(nums, nums[curPos], curPos+1)
        
        notoken = self.recursive(nums, preV, curPos+1)

        return max(token, notoken)

1.2.2、带记忆的递归（超时）

class Solution:
    def __init__(self) -> None:
        self.memo = None

    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        self.memo = [[-1]*n for _ in range(n)]

        return self.recursive(nums, -1, 0)

    def recursive(self, nums: List[int], preIdx: int, curPos: int) -> int:
        if curPos == len(nums):
            return 0
        
        if self.memo[preIdx+1][curPos] >= 0:
            return self.memo[preIdx+1][curPos] 

        token = 0
        if preIdx  nums[preIdx]:
            token = 1 + self.recursive(nums, curPos, curPos+1)
        
        notoken = self.recursive(nums, preIdx, curPos+1)
        self.memo[preIdx+1][curPos] = max(token, notoken)

        return max(token, notoken)

1.2.3、动态规划(dp[i] 的值代表 nums 前 i 个数字的最长子序列长度。)

转移方程： dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)。

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

        n = len(nums)
        dp = [1]*n  # 初始化，每个元素都是一个单独子序列

        # dp[i] 的值代表 nums 前 i 个数字的最长子序列长度。
        for i in range(n):
            for j in range(i):
                if nums[j] nums[k] ： 意味着nums[k] 可以接在前面所有长度的子序列之后，因此肯定是接到最长的后面（长度为 res），新子序列长度为res+1。 
 
初始状态：
 
    
令 tails列表所有值=0。
 
 
返回值：
 
    
返回 res ，即最长上升子子序列长度。
 
 
复杂度分析：
 
    
时间复杂度 O(NlogN)： 遍历 nums 列表需 O(N)，在每个 nums[i] 二分法需 O(logN)。
空间复杂度 O(N)： tails列表占用线性大小额外空间。
 
  
class Solution:
    def lengthOfLIS(self, nums: [int]) -> int:
        tails, res = [0] * len(nums), 0
        for num in nums:
            i, j = 0, res
            while i