数组最大和子数组暴力解法遇[-1,-2]失效，求问题排查

你的代码在处理全负数数组（比如输入[-1,-2]）时无法得到正确结果，核心问题是未将单个元素的子数组纳入初始的最大值比较逻辑。

问题细节拆解 #

当数组长度大于1时，你将maxSum初始化为Integer.MIN_VALUE，外层循环中每个i对应的初始sum是arr[i]，但这个值没有先和maxSum比较就直接进入内层循环：

• 以输入[-1,-2]为例：
  1. i=0时，sum=-1，此时未更新maxSum，直接进入j=1的循环，处理后sum变为-2，maxSum被更新为-2；
  2. i=1时，内层循环的j从2开始，根本不会执行，maxSum保持-2，但正确的最大子数组和应该是-1（对应单个元素[-1]）。

修复方案 #

方案一：补充单个元素的比较逻辑

在进入内层循环前，先将当前单个元素的和与maxSum对比更新：

public class MaxSumSubArray
{
    public int findSum (int[] arr)
    {
        int maxSum;
        if(arr.length == 1) {
            maxSum = arr[0];
        } else {
             maxSum = Integer.MIN_VALUE;
            for (int i = 0; i < arr.length; i++) {
                int sum = arr[i];
                // 先将单个元素的情况纳入最大值比较
                if (sum > maxSum) {
                    maxSum = sum;
                }
                for (int j = i + 1; j < arr.length; j++) {
                    if(arr[j] > sum + arr[j]) {
                        sum = arr[j];
                    } else {
                        sum = sum + arr[j];
                    }
                    if (sum > maxSum) {
                        maxSum = sum;
                    }
                }
            }
        }
        return maxSum;
    }
    public static void main(String[] args) {
        int[] arr1 = {-2,1,-3,4,-1,2,1,-5,4};
        int[] arr2 = {-1,-2};
        MaxSumSubArray subArray = new MaxSumSubArray();
        System.out.println("Max sum for arr1:"+ subArray.findSum(arr1)); // 输出6
        System.out.println("Max sum for arr2:"+ subArray.findSum(arr2)); // 输出-1
    }
}

方案二：统一初始化逻辑，简化代码

直接将maxSum初始化为数组第一个元素，同时用Math.max简化判断逻辑，无需区分数组长度：

public class MaxSumSubArray
{
    public int findSum (int[] arr)
    {
        int maxSum = arr[0];
        for (int i = 0; i < arr.length; i++) {
            int sum = arr[i];
            // 先检查单个元素的情况
            if (sum > maxSum) {
                maxSum = sum;
            }
            for (int j = i + 1; j < arr.length; j++) {
                sum = Math.max(arr[j], sum + arr[j]); // 简化原有的if-else判断
                if (sum > maxSum) {
                    maxSum = sum;
                }
            }
        }
        return maxSum;
    }
    public static void main(String[] args) {
        int[] arr1 = {-2,1,-3,4,-1,2,1,-5,4};
        int[] arr2 = {-1,-2};
        MaxSumSubArray subArray = new MaxSumSubArray();
        System.out.println("Max sum for arr1:"+ subArray.findSum(arr1)); // 输出6
        System.out.println("Max sum for arr2:"+ subArray.findSum(arr2)); // 输出-1
    }
}

两种方案都能解决全负数数组的问题，确保所有可能的子数组（包括单个元素）都被纳入最大值的计算范围。

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