力扣hot100:最大子数组和的两种高效方法：前缀和与Kadane算法(53)

最大子数组和问题是算法中的一个经典问题，即在给定整数数组中寻找连续子数组使其和达到最大（子数组不能为空）。本文将详细解析两种时间复杂度为 O(n)、空间复杂度为 O(1) 的精妙解法，并附上完整 Java 实现。

问题示例

给定数组 [-2,1,-3,4,-1,2,1,-5,4]，最大子数组和为 [4,-1,2,1]，其和为 6。

方法一：前缀和法（Prefix Sum）

核心思想

通过动态计算数组前缀和，并维护当前最小前缀和，用当前前缀和减去最小前缀和得到局部最大子数组和。

算法步骤

1. 初始化 temp 为当前前缀和（初始值为0）
2. 初始化 min 为最小前缀和（初始值为0）
3. 遍历数组：
   • 更新当前前缀和 temp += num
   • 计算当前子数组和：temp - min
   • 更新全局最大值 result
   • 更新最小前缀和 min

public int maxSubArrayT1(int[] nums) {int temp = 0;int min = 0;int result = Integer.MIN_VALUE;for (int num : nums) {temp += num;             // 更新当前前缀和result = Math.max(result, temp - min); // 更新全局最大值min = Math.min(temp, min);    // 更新最小前缀和}return result;
}

示例分析

以 [-2,1,-3] 为例：

方法二：Kadane算法（动态规划）

核心思想

通过动态维护当前连续子数组和，当和小于等于0时丢弃该子数组（因其无法增大后续和），同时全程更新最大值。

算法步骤

1. 初始化 temp 为当前子数组和（初始值为0）
2. 初始化 max 为全局最大值（初始值为 Integer.MIN_VALUE）
3. 遍历数组：
   • temp += nums[i]（累加当前值）
   • 更新 max = Math.max(max, temp)
   • 若 temp <= 0，重置 temp = 0（丢弃负贡献子数组）

public int maxSubArrayT2(int[] nums) {int max = Integer.MIN_VALUE;int temp = 0;for (int num : nums) {temp += num;          // 累加当前值max = Math.max(max, temp);  // 更新全局最大值if (temp <= 0) temp = 0;    // 若和为负则重置}return max;
}

示例分析

以 [-2,1,-3] 为例：

方法对比与总结

关键共同点：

• 时间复杂度 O(n)（只需一次遍历）
• 空间复杂度 O(1)（仅用常数变量）
• 均能正确处理全负数数组（如 [-3,-1,-2] 返回 -1）

两种方法都是高效解法，在实际面试或解题中：

• Kadane算法更简洁常用
• 前缀和法在需复用前缀信息时更灵活（如解决子矩阵最大和等问题）

两种解法简洁优雅，体现了算法设计中“维护关键状态，避免重复计算”的核心思想。理解其内在逻辑后，你能轻松应对各类子数组相关问题！