最大子数组和
Maximum Subarray
在一个可能有负数的数组中，找一个连续子数组，使它的元素和最大。
在力扣中练习题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
解题思路
Kadane · 以 i 结尾
前缀变成负数就丢掉，否则继续接
暴力枚举左右端点是 O(n²)。设 current 为以 nums[i] 结尾的最大子数组和，那么下一步只有两种选择：
- 接上前面的：
current + nums[i]； - 从当前数重新开始：
nums[i]。
取较大值。如果 current 已经是负数，接上它只会让结果更小，所以等价于丢掉前缀、从当前数重新开始。
自拟主例 [3,-5,4,2,-1,3]：接上 -5 后 current 变成 -2；遇到 4 时丢掉负前缀，从 4 重新开始，最后 4+2-1+3=8。
接上前面：3 + -5 = -2；全局最大 3。
- current
- -2
- best
- 3
best 单独记录所有 current 的最大值，因为最优子数组不一定在末尾结束。
接上前面：6 + -1 = 5；全局最大 6。
- current
- 5
- best
- 6
时间 O(n)，空间 O(1)。
易错点
- current 和 best 初始化为 0：数组全是负数时会返回 0，而不是最大负数。
- 只更新 current 不更新 best：答案可能停在数组中间。
- 认为 current 必须一直为正：它可以暂时为负，只要下一次加上 nums[i] 还能变大。
分治 · 跨中点合并
最大子数组要么在左半、要么在右半、要么跨中点
时间 O(n log n)，比 Kadane 慢；但分治框架可以扩展到二维最大子矩阵等更复杂的问题。
把数组从中点切开，最大子数组只有三种位置：完全在左半、完全在右半、跨过中点。
左右两半递归求解；跨中点的情况，分别从 mid 向左、从 mid+1 向右累加，记录最大后缀和与最大前缀和，相加就是跨中点的最优值。
时间 O(n log n)，递归栈 O(log n)。
- 1递归求解左半、右半。
- 2从 mid 向左累加，求最大后缀和。
- 3从 mid+1 向右累加，求最大前缀和。
- 4三者取最大。
易错点
- 跨中点时只取一边：必须同时包含 mid 和 mid+1 两侧的连续段。
- 递归终止条件写成 l >= r：单元素区间应返回该元素。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [3,-5,4,2,-1,3]从第一个数开始：current = best = 3；空子数组不允许，所以不能用 0 初始化。
- current
- 3
查看 C++ 代码
延伸阅读
- Kadane 的本质是“以 i 结尾”的状态压缩；和打家劫舍、乘积最大子数组共享同一套状态定义。
- 如果要求输出区间，需要额外记录起点；本页图解已经用窗口标出了当前区间。