给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
来源：力扣（LeetCode）
这个题的暴力解法就是从头开始遍历数据，找出以每个元素为头的连续数组的最大值，然后取所有结果的最大值。
这道题的关键在于怎么确定是否应该舍弃当前的连续数组，因为如果连续数组的下一个元素即使是负数也未必需要舍弃，就像题目中的示例那样。
具体的解题思路如下： ①将数组的第0个元素复制给变量 cur，表示当前最大连续数组的值； ②从数组 nums 的第一个元素开始遍历，如果当前最大值 cur 大于 0，说明 cur 加上当前遍历元素有可能超过最大值，相加并更新最大值 max_result； ③如果当前最大值小于 0，那么不论当前遍历元素与 0 的大小关系，cur + 当前元素 一定会比当前元素小，那么我们直接将当前元素赋值给 cur，并更新最大值 max_result。
代码如下：
def maxSubArray(self, nums: List[int]) -> int: cur = nums[0] max_result = cur for i in range(1, len(nums)): if cur > 0: cur += nums[i] max_result = max(max_result, cur) else: cur = nums[i] max_result = max(max_result, cur) return max_result分治法其实就是分类讨论，数组 nums 的最大子序和要么在左半边，要么在右半边，要么是穿过中间。而对于左右边的序列，情况也是一样，因此可以用递归处理。
具体来说，最大子序和主要从以下三部分子区间里元素的最大和得到：①子区间 [left, mid]；②子区间 [mid + 1, right]；③包含子区间 [mid , mid + 1] 的子区间。求取这三个部分的最大值即可。
代码来自力扣题解，具体如下：
def maxSubArray(self, nums: List[int]) -> int: size = len(nums) if size == 0: return 0 return self.__max_sub_array(nums, 0, size - 1) def __max_sub_array(self, nums, left, right): if left == right: return nums[left] mid = (left + right) >> 1 return max(self.__max_sub_array(nums, left, mid), self.__max_sub_array(nums, mid + 1, right), self.__max_cross_array(nums, left, mid, right)) def __max_cross_array(self, nums, left, mid, right): # 一定包含 nums[mid] 元素的最大连续子数组的和， # 思路是看看左边"扩散到底"，得到一个最大数，右边"扩散到底"得到一个最大数 # 然后再加上中间数 left_sum_max = 0 start_left = mid - 1 s1 = 0 while start_left >= left: s1 += nums[start_left] left_sum_max = max(left_sum_max, s1) start_left -= 1 right_sum_max = 0 start_right = mid + 1 s2 = 0 while start_right <= right: s2 += nums[start_right] right_sum_max = max(right_sum_max, s2) start_right += 1 return left_sum_max + nums[mid] + right_sum_max动态规划解法效果最佳
