LeetCode最大子数组和暴力解法：未通过测试用例如何解决？

首先明确：你的暴力解法逻辑是正确的，但无法通过所有测试用例，核心原因是时间复杂度太高。

你的代码是三层循环，时间复杂度为O(n³)，当测试用例中出现长度较大的数组（比如n=10000）时，运算量会达到10¹²级别，远远超出LeetCode的时间限制（通常允许的运算量在10⁸次以内），必然会超时——这不是代码逻辑错误，是算法效率的硬伤。

若要优化暴力解法（仅能提升部分效率，仍可能无法通过全部用例） #

可以通过前缀和数组将时间复杂度降到O(n²)，省去最内层的累加循环：

1. 先计算前缀和数组prefix，其中prefix[0] = 0，prefix[i]表示数组前i个元素的和（即nums[0] + nums[1] + ... + nums[i-1]）
2. 任意子数组nums[j...j+i-1]的和可以直接用prefix[j+i] - prefix[j]得到，无需逐一遍历累加

优化后的Java代码示例：

class Solution {
    public int maxSubArray(int[] nums) {
        int finalSum = Integer.MIN_VALUE;
        int n = nums.length;
        int[] prefix = new int[n + 1];
        // 构建前缀和数组
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        // 枚举所有子数组长度
        for (int i = 1; i <= n; i++) {
            // 枚举子数组起始位置
            for (int j = 0; j <= n - i; j++) {
                int sum = prefix[j + i] - prefix[j];
                if (sum > finalSum) {
                    finalSum = sum;
                }
            }
        }
        return finalSum;
    }
}

不过即使优化到O(n²)，当数组长度超过10000时，运算量仍会达到10⁸级别，大概率还是会超时，无法通过所有测试用例。

要通过所有测试用例的正确做法 #

必须使用时间复杂度更优的算法，比如：

• Kadane算法：时间复杂度O(n)，遍历一次数组，维护当前子数组的最大和，是该问题的最优解法
• 分治法：时间复杂度O(nlogn)，将数组分成左右两部分，分别求左右的最大子数组和，再求跨中间的最大子数组和，取三者最大值

比如Kadane算法的Java实现：

class Solution {
    public int maxSubArray(int[] nums) {
        int currentMax = nums[0];
        int finalSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            finalSum = Math.max(finalSum, currentMax);
        }
        return finalSum;
    }
}

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