子序列问题 - 动态规划、分治法

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

详解

1. 暴力遍历 O_(n)

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

        tmp_sum = nums[0]
        max_sum = tmp_sum

        for i in range(1,len(nums)):
            if tmp_sum > 0:
                tmp_sum = tmp_sum + nums[i]
                max_sum = max(tmp_sum, max_sum)
            else:
                max_sum = max(tmp_sum, max_sum, tmp_sum + nums[i], nums[i])
                tmp_sum = nums[i]
        return max_sum

2. 分治法 O_{(n logn)}

分成两半，则最大连续子数组要不在左边要不在右边。后面同理继续分。

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

        n = len(nums)
        if n == 1:
            return nums[0]
        else:
            # 递归计算左半边最大子序和
            max_left = self.maxSubArray(nums[0:n//2])
            # 递归计算右半边最大子序和
            max_right = self.maxSubArray(nums[n//2:n])

        # 计算中间的最大子序和
        # 从右到左计算左边的最大子序和
        max_l = nums[n//2 - 1]
        tmp_sum = 0
        for i in range(n//2-1,-1,-1):
            tmp_sum += nums[i]
            max_l = max(tmp_sum,max_l)

        # 从左到右计算右边的最大子序和
        max_r = nums[n//2]
        tmp_sum = 0
        for i in range(n//2,n):
            tmp_sum += nums[i]
            max_r = max(tmp_sum,max_r)

        return max(max_right,max_left,max_l + max_r)

3. 动态规划 O_(n)

• 状态定义
  dp_[i] 结尾为 nums[i]的连续子数组的最大和
• 状态转移方程
  • dp_[i−1] ≥ 0
    dp_[i−1] = dp[i−1] + nums[i]
  • dp_[i−1] < 0
    dp_[i−1] = nums[i]
• 初始值
  dp[0] = nums[0]
• 输出
  所有 dp[i] 的最大值

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

​

300. 最长上升子序列

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