如何修改现有Java代码解决全负数数组的最大子数组和问题？

你的代码在常规数组下运行正常，但全负数数组（如[-2,-1]）会返回0而非正确值，核心问题是maxSum初始值设为0，导致所有负数子数组和都无法超过它，最终错误返回0。以下是不改变双重循环思路的小幅修改方案：

修改思路 #

1. 将maxSum的初始值从0改为数组第一个元素，直接以数组内元素作为基准，避免0干扰全负数场景。
2. 扩展外层循环范围，同时在每次外层循环开始时，先比较当前单个元素与maxSum，确保单个元素的最大值（比如全负数数组中最大的那个负数）被捕获。
3. 去掉原代码末尾单独比较最后一个元素的逻辑，因为扩展后的循环已经覆盖了所有单个元素的情况。

修改后的代码 #

class Solution {
    public int maxSubArray(int[] nums) {
        int sum;
        // 初始化maxSum为数组第一个元素，处理全负数场景
        int maxSum = nums[0];
        
        for (int i = 0; i < nums.length; i++) {
            // 先检查当前单个元素是否为更大值
            if (nums[i] > maxSum) {
                maxSum = nums[i];
            }
            sum = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                if (sum > maxSum) {
                    maxSum = sum;
                }
            }
        }
        return maxSum;
    }
}

验证场景 #

• 常规输入nums = [-2,1,-3,4,-1,2,1,-5,4]：代码会计算到子数组[4,-1,2,1]的和为6，正确返回6。
• 全负数输入nums = [-2,-1]：初始maxSum为-2，外层循环i=0时，计算子数组[-2,-1]和为-3，不更新maxSum；i=1时，比较nums[1]=-1大于当前maxSum(-2)，更新maxSum为-1，最终返回-1，符合预期。

内容的提问来源于stack exchange，提问作者Shreyansh