本文共 4355 字，大约阅读时间需要 14 分钟。
"""给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。"""
就这个例子来说，一共有9个数字，我们把所有的排列组合列出来，然后求出最大值。按照排列组合的数学算法，以第i个数字结尾的排列组合，一共有45个组合，如果有n个数字，时间复杂度是O(n^2)，这样的时间复杂度是明显不能接受的。
首先需要把这个问题分解成最优子问题来解。最主要的思路就是将组合进行分类，分解成数量较少的几个子问题。在这里我们一共有9个数字，顺理成章的我们把组合分解成9个小组的组合。
第一个子组合是以第一个数字结尾的连续序列，也就是[-2]，最大值-2
第二个子组合是以第二个数字结尾的连续序列，也就是[-2,1], [1]，最大值1
第三个子组合是以第三个数字结尾的连续序列，也就是[-2,1,3], [1,3], [3]，最大值4
以此类推…
如果我们能够得到每一个子组合的最优解，也就是子序列的最大值，整体的最大值就可以通过比较这9个子组合的最大值来得到了。现在我们找到了最优子问题，重叠子问题在哪呢？那就得细心比较一下每个子问题。
从第二个子组合和第三个子组合可以看到，组合3只是在组合2的基础上每一个数组后面添加第3个数字，也就是3，然后增加一个只有第三个数字的数组[3]。这样两个组合之间的关系就出现了，可是我们不关心这个序列是怎么生成的，只是关心最大值之间的关系。我们将子组合三分成两种情况：
如果第二个序列的最大值大于0，那么最大值1就比最大值-2要大，反之最大值-2较大。这样，我们就通过第二个组合的最大值和第三个数字，就得到了第三个组合的最大值。因为第二个组合的结果被重复用到了，所以符合这个重叠子问题的定义。通俗来讲这个问题就变成了，第i个子组合可以通过第i-1个子组合的最大值和第i个数字获得，如果第i-1个子组合的最大值没法给第i个数字带来正增益，我们就抛弃掉前面的子组合，自己就是最大的了。
看代码，只需要一个变量submax保存前面子组合的最大值，另外一个realmax保存全局最大值。
class Solution: def maxSubArray(self, nums: List[int]) -> int: realmax = submax = nums[0] for i in nums[1:]: if submax > 0: submax += i else: submax = i realmax = max(realmax, submax) return realmax
该算法通用且简单：遍历数组并在每个步骤中更新：
class Solution: # Kadane算法: 和上面的动态规划方法思路很像 def maxSubArray3(self, nums: List[int]) -> int: realmax = currmax = nums[0] for i in nums: currmax = max(i, currmax + i) realmax = max(realmax, currmax) return realmax
分治法是将整个数组切分成几个小组，每个小组然后再切分成几个更小的小组，一直到不能继续切分也就是只剩一个数字为止。然后每个小组会计算出最优值，汇报给上一级的小组，一级一级汇报，上级拿到下级的汇报找到最大值，得到最终的结果。 和合并排序的算法类似，先切分，再合并结果。
这个问题中的关键就是如何切分这些组合才能使每个小组之间不会有重复的组合（有重复的组合意味着有重复的计算量）。
首先是切分分组方法，就这个案例中的例子来，我们有一个数组[-2,1,-3,4,-1,2,1,-5,4]，一共有9个元素，我们center=(start + end) / 2这个原则，得到中间元素的索引为4，也就是-1，拆分成三个组合：
以上的三个组合内的序列没有任何的重复的部分，而且一起构成所有子序列的全集，计算出这个三个子集合的最大值，然后取其中的最大值，就是这个问题的答案了。
然而前两个子组合可以用递归来解决，一个函数就搞定，第三个跨中心的组合应该怎么计算最大值呢？
答案就是：
在计算过程中，累加和比较的过程是关键操作，一个长度为n的数组在递归的每一层都会进行n次操作，分治法的递归层级在logN级别，所以整体的时间复杂度是O(nlogn)，在时间效率上不如动态规划的O(n)复杂度（在leetcode网页上测试，出现超时）。
class Solution: def maxSubArray(self, nums: List[int]) -> int: def maxSubArrayDivideWithBorder(nums, start, end): # 1. 递归的结束出口：只有一个元素， if start == end: return nums[start] # 2. 计算中间值、左侧子序列最大值、右侧子序列最大值 center = (start + end) // 2 leftMax = maxSubArrayDivideWithBorder(nums, start, center) rightMax = maxSubArrayDivideWithBorder(nums, center + 1, end) # 3. 计算横跨中心位置的两个子序列的最大值 leftCrossSum = 0 leftCrossMax = nums[center] for i in range(center, -1, -1): # 以center下标开始，逆序求和 leftCrossSum += nums[i] leftCrossMax = max(leftCrossMax, leftCrossSum) rightCrossSum = 0 rightCrossMax = nums[center + 1] for i in range(center + 1, len(nums)): # 以center+1下标开始，顺序求和 rightCrossSum += nums[i] rightCrossMax = max(rightCrossMax, rightCrossSum) crossMax = leftCrossMax + rightCrossMax # 4. 计算最大值：比较左侧子序列、右侧子序列、横跨子序列三者的最值 return max(crossMax, max(leftMax, rightMax)) return maxSubArrayDivideWithBorder(nums, 0, len(nums) - 1)
不用说了，这种方法虽然没错，在leetcode网页上运行，也是超时。
# 暴力解法:穷举所有的子区间(时间复杂度：O(N^2)，空间复杂度O(1))from typing import Listclass Solution: # leetcode上，当测试数据较大时，会出现超时 def maxSubArray1(self, nums: List[int]) -> int: length = len(nums) res = nums[0] for i in range(length): sum = 0 for j in range(i + 1, length): sum += nums[j] res = max(sum, res) return res
转载地址：http://btdh.baihongyu.com/