企业官网建设流程全解析

LeetCode Hot100：53. 最大子数组和

文章摘要

这篇文章是用来记录我练习 LeetCode Hot100 第 53 题“最大子数组和”的思路变化：从尝试滑动窗口、枚举所有连续子数组，到用动态规划在一次遍历中求解，并补充官方进阶分治解法中的四个区间状态及合并公式。

一、题目与最初的想法

题目要求在整数数组中找出一个非空、连续的子数组，使它的元素和最大。见下图：

我最初看到这道题时，想用滑动窗口来解决，但这题的数组允许出现负数。加入一个元素后，窗口和可能变大，也可能变小；移除左端元素也一样。因此，窗口和不具备常见滑动窗口题目中的单调性，不能仅根据当前窗口和判断应该移动哪一端。继续套用滑动窗口会让边界判断变复杂，也难以保证不漏掉答案。

二、先枚举所有连续子数组

之后我想到固定左端点、不断右移右端点，把所有连续子数组都枚举出来。这个思路直接，但时间复杂度是平方级。

固定起点left，从left开始累加每一个可能的终点。这样每个连续子数组都会被检查一次：

classSolution{publicintmaxSubArray(int[]nums){// 题目保证数组非空。intanswer=nums[0];for(intleft=0;left<nums.length;left++){intsum=0;for(intright=left;right<nums.length;right++){sum+=nums[right];answer=Math.max(answer,sum);}}returnanswer;}}

外层选择起点，内层枚举终点，时间复杂度为O(n²)，额外空间复杂度为O(1)。这种写法比逐个重新求和更高效，因为内层循环复用了前一步的子数组和，但在数组长度较大时仍然会超时。

三、动态规划：只保留以当前位置结尾的最大和

动态规划来优化时间复杂度的关键是不用像双重 for 循环一样，在每一步都枚举起始位置。遍历到下标i时，只需要知道：**在以 nums[i] 结尾的连续子数组中，最大和是多少？**官方题解里的pre就用来保存这个值：每轮循环更新后，pre表示以当前元素结尾的最大子数组和。

官方题解链接：https://leetcode.cn/problems/maximum-subarray/solutions/228009/zui-da-zi-xu-he-by-leetcode-solution/

我们用pre表示以nums[i]结尾的最大连续子数组和。以i结尾的子数组只有两种构造方式：

1. 从nums[i]重新开始，和为nums[i]；
2. 把nums[i]接到以i - 1结尾的最佳子数组后面，和为pre(i - 1) + nums[i]。

所以状态转移为：

pre = max(nums[i], pre(i - 1) + nums[i])

遍历过程中，各个位置的prei再共同决定全局答案：

answer = max(pre0, pre1, ..., pre(n - 1))

下图按题目示例列出了每一步的状态。到下标6时，以当前位置结尾的最大和达到6，对应[4, -1, 2, 1]。

Java 实现

classSolution{publicintmaxSubArray(int[]nums){// 题目保证 nums 非空。intpre=0;intanswer=nums[0];for(intx:nums){pre=Math.max(pre+x,x);answer=Math.max(answer,pre);}returnanswer;}}

pre只保存当前下标对应的状态，因此不需要保存整张 DP 数组。时间复杂度为O(n)，额外空间复杂度为O(1)。

四、进阶：分治法与四个区间状态

力扣官方题解还给出了分治解法。它把区间不断拆成左右两半，再将子区间的结果合并。合并得到的结果可能是：
1.跨越左右边界的最大子数组；
2.最大和子数组完全在左区间
3.最大和子数组完全在右区间

因此，对每个区间[left, right]保存四个值：

设左右子区间的状态分别为leftStatus和rightStatus。合并时：

iSum = leftStatus.iSum + rightStatus.iSum lSum = max(leftStatus.lSum, leftStatus.iSum + rightStatus.lSum) rSum = max(rightStatus.rSum, rightStatus.iSum + leftStatus.rSum) mSum = max(leftStatus.mSum, rightStatus.mSum, leftStatus.rSum + rightStatus.lSum)

后三个候选分别覆盖“最大子数组完全在左边”、“完全在右边”和“跨越左右边界”。其中跨界候选必须使用左区间的最大后缀rSum与右区间的最大前缀lSum拼接。

这个时候可能会有一点疑惑，我们已经有了 mSum，也就是左边和右边各自的最大和，那 lSum 和 rSum 的作用是什么？我们看下边的例子：

例如左区间[5, -100, 4]的最大子数组和是5，但最大后缀是4；右区间[3, -100, 6]的最大子数组和是6，但最大前缀是3。合并时，跨界候选为4 + 3 = 7，大于左右各自的最大子数组和。即在合并两个小数组得到新数组时，我们要考虑之前得到的最大和，是否在合并后还可以组成连续的子数组？

这里不展开完整代码，只把注意力放在状态如何合并：区间总和由左右总和相加得到；最大前缀和、最大后缀和分别考虑 “完全落在一侧“ 或”跨过分界线“；最大子数组和则在左侧、右侧和跨界三种候选中取最大值。理解这几个关系后，可以再尝试独立补出递归和状态合并过程。

每个区间的合并只做常数次计算，递归会处理线性数量的区间节点，因此时间复杂度为O(n)；递归栈的额外空间复杂度为O(log n)。对于本题，Kadane 写法更短，也只使用常数额外空间；分治法的价值在于理解如何把区间摘要合并起来，这种状态设计也能用于支持区间查询或更新的扩展问题。

五、容易忽略的边界

• 数组非空，子数组也必须非空。answer初始化为nums[0]，不能初始化为0，否则全负数数组会错误地返回0。
• 连续性不能丢。状态只允许延续到相邻的前一个位置，不能跳过中间元素。
• 滑动窗口没有这里需要的单调性。负数使窗口扩张或收缩后的和都可能朝任一方向变化，不能直接用常见的窗口和条件决定移动方向。

参考资料

1. 力扣第 53 题：最大子数组和：题目链接
2. 力扣官方题解：最大子数组和（动态规划与分治）：题解链接