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数组，从而实现了极致的空间优化。

二、 算法演进对比

在解决最大子区间和问题时，不同算法的效率差异极其显著：

三、 核心代码逻辑推导

当前提供的源码逻辑非常精简，其运行时的决策机制可以定量分析为：

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循环内部的演进状态如下表所示：

五、源码实现

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 的增长而发生任何改变，空间消耗恒定为常数阶。