题目

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 最大子序和 - 图2 的解法，尝试使用更为精妙的分治法求解。

方案一（动态规划）

  1. class Solution:
  2.     def maxSubArray(self, nums: List[int]) -> int:
  3.         # 动态规划
  4.         if not nums:
  5.             return 0
  6.         # dp[i][j] 表示区间 nums[i:j] 的和的最大值 i < j，所以最终 dp table 为一个三角形
  7.         dp = [[-float('inf')] * len(nums) for i in range(len(nums)) ]
  9.         # init
  10.         res = -float('inf')
  11.         for i in range(len(nums)):
  12.             dp[i][i] = nums[i]
  13.             res = max(res, dp[i][i])
  14.             if i == 0: 
  15.                 continue
  16.             dp[0][i] = dp[0][i - 1] + nums[i]
  17.             res = max(res, dp[0][i])
  19.         # dp 阶段
  20.         for i in range(1, len(nums)):
  21.             for j in range(i + 1, len(nums)):
  22.                 dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 1]) + nums[j]
  23.                 res = max(res, dp[i][j])
  25.         return res
  • 超出内存限制
  • 时间复杂度最大子序和 - 图3
  • 空间复杂度最大子序和 - 图4

    方案二（动态规划）

  1. class Solution:
  2.     def maxSubArray(self, nums: List[int]) -> int:
  3.         # dp[i] 表示以当前元素结尾的子数组的最大值, dp[i + 1] = max(nums[i + 1], dp[i] + nums[i + 1])
  4.         dp = []
  5.         # init
  6.         dp.append(nums[0])
  8.         # dp
  9.         for i in range(1, len(nums)):
  10.             dp.append(max(dp[i - 1] + nums[i], nums[i]))
  12.         return max(dp)
  • 与方案一相比仅仅是换了一个 dp 的思路；
  • 时间复杂度最大子序和 - 图5
  • 空间复杂度最大子序和 - 图6

    原地修改数组使得空间复杂度为最大子序和 - 图7

  1. class Solution:
  2.     def maxSubArray(self, nums: List[int]) -> int:
  3.         # dp[i] 表示以当前元素结尾的子数组的最大值, dp[i + 1] = max(nums[i + 1], dp[i] + nums[i + 1])
  4.         for i in range(1, len(nums)):
  5.             nums[i] = max(nums[i - 1] + nums[i], nums[i])
  7.         return max(nums)

方案三（分治）

查阅下述第二个链接，感觉没有动态规划简单

原文

https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/278/classic-problems/1236/
https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode/