最大子数组和算法解析：暴力、动态规划与贪心（Java）

注意：当数组中所有元素都是负数时，需特殊处理（如初始化为第一个元素）。

代码实现

解法 1：暴力解法（参考）

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int maxSum = nums[0];
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
        return maxSum;
    }
}
// 时间复杂度：O(n²)，空间复杂度：O(1)

解法 2：动态规划（推荐）

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int preSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < n; i++) {
            preSum = Math.max(preSum + nums[i], nums[i]);
            maxSum = Math.max(maxSum, preSum);
        }
        return maxSum;
    }
}
// 时间复杂度：O(n)，空间复杂度：O(1)

解法 3：贪心算法（推荐）

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int currentSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < n; i++) {
            currentSum = Math.max(currentSum + nums[i], nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}
// 时间复杂度：O(n)，空间复杂度：O(1)

关键细节

1. 数组全为负数的情况：必须将 maxSum 初始化为 nums[0]，避免结果为 0。
2. 子数组的连续性：必须是连续的，不能跳过元素。
3. 贪心算法的重置时机：只有当 currentSum 为负数时，才重置为当前元素。
4. 动态规划的状态定义：必须是'以第 i 个元素结尾'，否则无法保证连续性。

拓展思考

• 要求返回最大子数组的起始和结束索引；
• 最大子数组和的个数；
• 二维数组的最大子数组和。

其中，'返回最大子数组的起始和结束索引'是最常考的延伸，可基于贪心或动态规划修改代码实现。

总结

最大子数组和是贪心和动态规划的经典入门题。

• 暴力解法：效率低，适合入门；
• 动态规划：通过状态定义和转移方程，实现 O(n) 时间复杂度，空间可优化到 O(1)；
• 贪心算法：逻辑简洁，效率最高。

建议先动手写一遍暴力解法，再逐步优化，注意规避常见坑（全负数、连续性）。