300. 最长递增子序列

• 思路
  • example
  • 子序列：不需要连续, LIS
  • 单串DP

dp[i]: 以ith结尾

• 复杂度. 时间：, 空间:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0] = 1
        for i in range(1, len(nums)):
            dp[i] = 1
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums) 
        dp = [1 for _ in range(n)] 
        res = dp[0]
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1) 
            res = max(res, dp[i]) 
        return res  

• 贪心+二分(左边界），时间
  

dp[i]: 长度为i的LIS的最后一个元素的最小可能值。这样就能构造尽可能长的递增子序列。
初始化dp[0] = float('-inf')
dp是严格递增的 （单调栈?)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def BinarySearch_insert(dp, target):
            left, right = 0, len(dp)-1
            while left <= right:
                mid = left + (right - left) // 2
                if dp[mid] > target:
                    right = mid - 1
                elif dp[mid] < target:
                    left = mid + 1
                else: # nums[mid] == target
                    right = mid - 1
            return left  # it's possible to have left = len(dp) + 1
        n = len(nums)
        dp = [float('-inf')]
        res = 0
        for i in range(n):
            # 在dp中找最小的index使得dp[index] >= nums[i], 二分找左边界
            insert_idx = BinarySearch_insert(dp, nums[i])
            if insert_idx == len(dp):
                dp.append(nums[i])
                res += 1
            else:
                dp[insert_idx] = nums[i]
        return res

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def binarySearch(dp, target):
            n = len(dp)
            left, right = 0, n-1
            while left <= right:
                mid = left + (right - left) // 2
                if dp[mid] < target:
                    left = mid + 1
                elif dp[mid] > target:
                    right = mid - 1
                else:
                    right = mid - 1
            return left
        n = len(nums)
        dp = [-float('inf')]
        for i in range(n):
            idx = binarySearch(dp, nums[i])
            if idx == len(dp):
                dp.append(nums[i])
            dp[idx] = nums[i] 
        return len(dp)-1

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums) 
        dp = [-float('inf')]  
        for i in range(n):
            idx = bisect_left(dp, nums[i]) 
            if idx == len(dp):
                dp.append(nums[i]) 
            else:
                dp[idx] = nums[i] 
        return len(dp) - 1

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def BinarySearch(nums, target):
            n = len(nums)
            left, right = 0, n-1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left 
        n = len(nums)
        stack = [nums[0]]
        for i in range(1, n):
            idx = BinarySearch(stack, nums[i]) 
            if idx == len(stack):
                stack.append(nums[i]) 
            else:
                stack[idx] = nums[i] 
        return len(stack) 

674. 最长连续递增序列

• 思路
  • example
  • 连续子序列, LCIS

dp[i]：以ith结尾

• 复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1 for _ in range(n)]
        dp[0] = 1
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                dp[i] = dp[i-1] + 1
        return max(dp)

• 滑窗

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = 0, 1 
        res = 1
        while right < n:
            if nums[right] > nums[right-1]:
                res = max(res, right - left + 1)
            else:
                left = right 
            right += 1
        return res  

• 贪心
• 小结：连续问题--当前状态只跟前一步有关；不连续问题--当前状态跟前几步有关。

718. 最长重复子数组

• 思路
  • example
  • 连续子序列
  • 两个数组匹配，二维DP

dp[i][j]: nums1 以ith结尾，nums2以 jth结尾
如果nums1[i] != nums2[j],那么dp[i][j] = 0.

• 复杂度. 时间：O(mn), 空间: O(mn)

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp =[[0] * n for _ in range(m)]
        res = 0
        for j in range(n):
            if nums1[0] == nums2[j]:
                dp[0][j] = 1
                res = 1
        for i in range(m):
            if nums1[i] == nums2[0]:
                dp[i][0] = 1
                res = 1
        for i in range(1, m):
            for j in range(1, n):
                if nums1[i] == nums2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1 
                res = max(res, dp[i][j])
        return res  

• 可空间优化
• 可以定义dp size (m+1)*(n+1), 简化初始化过程

# dp[i][j]: 以i-1结尾，j-1结尾的最长公共后缀的长度
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        dp[0][0] = 0
        res = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                res = max(res, dp[i][j])
        return res 

354. 俄罗斯套娃信封问题

• 思路
  • example
  • 注意：长宽相同无法嵌套 (严格包含才能套）
  • 二维 LIS

对宽度 w 从小到大排序，确保了 w 这个维度可以互相嵌套
当宽度w相同时，按h从大到小排序，确保LIS不会出现宽度w相同的情况 (否则在同一宽度情况下，会有嵌套关系。)
按以上方法排序后只保留h维度，运用一维LIS方法找LIS即可

• 复杂度. 时间：O(n logn), 空间: O(n)

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        def LIS(nums): 
            n = len(nums)
            dp = [-float('inf')]
            for i in range(n):
                idx = bisect_left(dp, nums[i])
                if idx == len(dp):
                    dp.append(nums[i])
                dp[idx] = nums[i]
            return len(dp)-1
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        return LIS([x[1] for x in envelopes])

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        def LIS(nums): 
            n = len(nums) 
            dp = [-float('inf')] 
            for i in range(n):
                index = bisect_left(dp, nums[i]) 
                if index == len(dp):
                    dp.append(nums[i]) 
                dp[index] = nums[i] 
            return len(dp) - 1
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        return LIS([x[1] for x in envelopes])