hot100 最大子数组和(53)
本题采用优化后的动态规划算法（即 Kadane 算法）解决“最大子数组和”问题。其核心本质是在单次线性扫描中，通过状态转移方程实时决定是“将当前元素并入先前子数组”还是“以当前元素为起点另起子数组”，从而将空间复杂度由常规动态规划的 O(n) 降低至 O(1)。该算法通过抛弃累加和为负的历史区间，最终走向是通过一次遍历直接锁定全局最大的连续子数组之和。
一、 问题本质与数据模型
对于给定的整数数组 nums，设其长度为 n。一个连续子数组可以表示为区间 [j, i]，其目标是最大化该区间内所有元素的累加和。
为了高效求解，引入动态规划模型。设dp[i]表示以位置 i 的元素结尾的连续子数组的最大和。根据连续性的物理约束，dp[i]的状态仅取决于前一个位置的状态dp[i-1]与当前元素nums[i]的关系：
如果
dp[i-1]为正数，则它对当前元素有增益作用，应当累加：dp[i] = dp[i-1] + nums[i]如果
dp[i-1]为负数，则它对当前元素有减益作用，应当丢弃先前的区间，重新以当前元素作为子数组的起点：dp[i] = nums[i]
由此得到标准状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])
由于dp[i]的计算只与dp[i-1]相关，代码中利用单个滚动变量max1代替了整个dp数组，从而实现了极致的空间优化。
二、 算法演进对比
在解决最大子区间和问题时，不同算法的效率差异极其显著：
| 解法名称 | 时间复杂度 | 空间复杂度 | 核心原理 | 物理瓶颈 |
|---|---|---|---|---|
| 暴力三重循环 | O(n^3) | O(1) | 枚举所有可能的左右边界，再嵌套循环计算区间和 | 重复求和导致时间开销呈立方级增长 |
| 前缀和优化暴力 | O(n^2) | O(n) | 预计算前缀和数组，双重循环枚举边界利用差值求区间和 | 边界组合数仍为平方级，大样本下必然超时 |
| 标准分治法 | O(n log n) | O(log n) | 递归将数组一分为二，最大和可能在左半边、右半边或跨越中点 | 递归调用带来栈空间消耗，时空效率非最优 |
| 动态规划（当前解法） | O(n) | O(1) | 滚动变量维护“以当前位置结尾的最大和”，用全局变量捕捉历史最大值 | 无，达到时空复杂度的理论极限 |
三、 核心代码逻辑推导
当前提供的源码逻辑非常精简，其运行时的决策机制可以定量分析为：
1. 局部状态迭代：max1 = Math.max(max1 + x, x)
变量
max1动态等价于数学模型中的dp[i]。每次循环引入新元素
x时，计算max1 + x。如果max1 + x < x，在数学上等价于max1 < 0。结论：只要先前的连续累加和变成了负数，无论下一个元素
x是正是负，加上一个负数都会让x变得更小。因此算法会立即斩断历史区间，使max1直接重置为x。
2. 全局状态捕捉：ans = Math.max(max1, ans)
变量
ans用于存储遍历全过程中出现过的max1的最大历史峰值。因为最大子数组可能在数组的任何位置结束（不一定包含最后一个元素），所以必须在每一步迭代中都用
ans进行同步更新。
四、 算法执行状态机步进示例
以输入数据nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]为例，初始化ans = nums[0] = -2，max1 = 0。代码在for循环内部的演进状态如下表所示：
| 步骤 | 当前元素 x | max1 + x 的数值 | max1 更新结果：max(max1 + x, x) | ans 更新结果：max(max1, ans) | 物理状态说明 |
|---|---|---|---|---|---|
| 1 | -2 | 0 + (-2) = -2 | max(-2, -2) =-2 | max(-2, -2) =-2 | 初始第一个元素 |
| 2 | 1 | -2 + 1 = -1 | max(-1, 1) =1 | max(1, -2) =1 | 丢弃负增益-2，以1重新开始 |
| 3 | -3 | 1 + (-3) = -2 | max(-2, -3) =-2 | max(-2, 1) =1 | 引入负数，局部和下降 |
| 4 | 4 | -2 + 4 = 2 | max(2, 4) =4 | max(4, 1) =4 | 丢弃负增益-2，以4重新开始 |
| 5 | -1 | 4 + (-1) = 3 | max(3, -1) =3 | max(3, 4) =4 | 引入-1，局部和下降但依然为正 |
| 6 | 2 | 3 + 2 = 5 | max(5, 2) =5 | max(5, 4) =5 | 获得正增益，局部和上升，更新全局最大 |
| 7 | 1 | 5 + 1 = 6 | max(6, 1) =6 | max(6, 5) =6 | 获得正增益，产生全局最优解区间 |
| 8 | -5 | 6 + (-5) = 1 | max(1, -5) =1 | max(1, 6) =6 | 引入大负数，局部和严重下降 |
| 9 | 4 | 1 + 4 = 5 | max(5, 4) =5 | max(5, 6) =6 | 获得正增益，但未超越历史峰值 |
五、源码实现
class Solution { public int maxSubArray(int[] nums) { // 边界条件处理：若数组为空则返回 0 if (nums == null || nums.length == 0) { return 0; } // ans 初始化为数组第一个元素，用来保存全局最大子数组和 int ans = nums[0]; // max1 滚动维护以当前元素结尾的最大连续子数组和 int max1 = 0; // 线性扫描整个数组 for (int x : nums) { // 核心状态转移： // 如果历史累加和 max1 为负数，则 max1 + x 必然小于 x，此时 max1 自动更新为 x（即重新起头） // 如果历史累加和 max1 为正数，则 max1 + x 必然大于 x，此时 max1 继续累加当前值 x max1 = Math.max(max1 + x, x); // 每一步都将当前局部最优解与全局最优解进行比对并更新 ans = Math.max(max1, ans); } return ans; } }六、 复杂度分析
1. 时间复杂度：O(n)
分析：算法结构仅包含单层
for-each循环。该循环从索引0顺序前进至n-1，对数组nums进行了单次完整的线性遍历。在单次迭代内部，只执行了两次常数级别的逻辑判断与赋值操作（Math.max）。结论：总计算耗时与输入数组的长度 n 呈严格的线性正比关系。
2. 空间复杂度：O(1)
分析：传统的动态规划需要声明一个长度为 n 的
dp数组来保存各个阶段的状态值。而该解法对空间进行了极度压缩，仅开辟了ans和max1两个基础类型的整型变量用于状态滚动与结果留存。结论：程序运行期间分配的内存不随输入数据规模 n 的增长而发生任何改变，空间消耗恒定为常数阶。