本题采用优化后的动态规划算法即 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] -2max1 0。代码在for循环内部的演进状态如下表所示步骤当前元素 xmax1 x 的数值max1 更新结果max(max1 x, x)ans 更新结果max(max1, ans)物理状态说明1-20 (-2) -2max(-2, -2) -2max(-2, -2) -2初始第一个元素21-2 1 -1max(-1, 1) 1max(1, -2) 1丢弃负增益-2以1重新开始3-31 (-3) -2max(-2, -3) -2max(-2, 1) 1引入负数局部和下降44-2 4 2max(2, 4) 4max(4, 1) 4丢弃负增益-2以4重新开始5-14 (-1) 3max(3, -1) 3max(3, 4) 4引入-1局部和下降但依然为正623 2 5max(5, 2) 5max(5, 4) 5获得正增益局部和上升更新全局最大715 1 6max(6, 1) 6max(6, 5) 6获得正增益产生全局最优解区间8-56 (-5) 1max(1, -5) 1max(1, 6) 6引入大负数局部和严重下降941 4 5max(5, 4) 5max(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 的增长而发生任何改变空间消耗恒定为常数阶。