关于Subarray Sum问题中Minimal Prefix Sum应用的原理与示例问询

先明确前缀和的基础定义：对于数组nums，我们定义前缀和数组pre_sum，其中pre_sum[0] = 0，pre_sum[i]表示nums[0]到nums[i-1]的累加和。那么任意子数组nums[j..i-1]的和可以表示为pre_sum[i] - pre_sum[j]（j < i）。这个公式是所有前缀和优化的核心。

一、用最小前缀和求最大子数组和 #

要找到整个数组中的最大子数组和，本质上是对每个i，找到j < i使得pre_sum[i] - pre_sum[j]最大。因为pre_sum[i]是固定值，要让差值最大，只需要找到i之前最小的pre_sum[j]即可。

示例拆解： #

以数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例：

1. 初始化：pre_sum = 0（对应pre_sum[0]），当前最小前缀和min_pre = 0，最大子数组和max_sum = -∞
2. 遍历数组，逐步计算前缀和并更新：
   • 第1个元素-2：pre_sum = 0 + (-2) = -2，当前子数组和为-2 - 0 = -2，max_sum更新为-2；min_pre更新为min(0, -2) = -2
   • 第2个元素1：pre_sum = -2 + 1 = -1，当前子数组和为-1 - (-2) = 1，max_sum更新为1；min_pre保持-2
   • 第3个元素-3：pre_sum = -1 + (-3) = -4，当前子数组和为-4 - (-2) = -2，max_sum不变；min_pre更新为-4
   • 第4个元素4：pre_sum = -4 + 4 = 0，当前子数组和为0 - (-4) = 4，max_sum更新为4；min_pre保持-4
   • 第5个元素-1：pre_sum = 0 + (-1) = -1，当前子数组和为-1 - (-4) = 3，max_sum不变；min_pre保持-4
   • 第6个元素2：pre_sum = -1 + 2 = 1，当前子数组和为1 - (-4) = 5，max_sum更新为5；min_pre保持-4
   • 第7个元素1：pre_sum = 1 + 1 = 2，当前子数组和为2 - (-4) = 6，max_sum更新为6；min_pre保持-4
   • 第8个元素-5：pre_sum = 2 + (-5) = -3，当前子数组和为-3 - (-4) = 1，max_sum不变；min_pre保持-4
   • 第9个元素4：pre_sum = -3 + 4 = 1，当前子数组和为1 - (-4) = 5，max_sum不变
3. 最终得到最大子数组和为6，对应子数组[4, -1, 2, 1]

这里的关键优化是：不需要存储完整的前缀和数组，只需要在遍历过程中动态维护当前的最小前缀和，空间复杂度从O(n)降到O(1)，时间复杂度始终是O(n)。

二、延伸：用最大前缀和求最小子数组和 #

同理，如果要找最小子数组和，我们需要让pre_sum[i] - pre_sum[j]最小。此时对于每个i，只需要找到i之前最大的pre_sum[j]即可。

示例拆解： #

以数组 [2, -1, 3, -4, 1] 为例：

1. 初始化：pre_sum = 0，当前最大前缀和max_pre = 0，最小子数组和min_sum = +∞
2. 遍历数组：
   • 第1个元素2：pre_sum = 0 + 2 = 2，当前子数组和为2 - 0 = 2，min_sum更新为2；max_pre更新为2
   • 第2个元素-1：pre_sum = 2 + (-1) = 1，当前子数组和为1 - 2 = -1，min_sum更新为-1；max_pre保持2
   • 第3个元素3：pre_sum = 1 + 3 = 4，当前子数组和为4 - 2 = 2，min_sum不变；max_pre更新为4
   • 第4个元素-4：pre_sum = 4 + (-4) = 0，当前子数组和为0 - 4 = -4，min_sum更新为-4；max_pre保持4
   • 第5个元素1：pre_sum = 0 + 1 = 1，当前子数组和为1 - 4 = -3，min_sum不变
3. 最终得到最小子数组和为-4，对应子数组[3, -4]

核心总结 #

• 子数组和的本质是当前前缀和与历史前缀和的差值
• 求最大子数组和：对每个当前前缀和，找历史中最小的前缀和，差值即为以当前位置结尾的最大子数组和
• 求最小子数组和：对每个当前前缀和，找历史中最大的前缀和，差值即为以当前位置结尾的最小子数组和
• 优化关键：遍历过程中动态维护需要的历史极值（最小/最大前缀和），无需存储全部前缀和，实现O(n)时间+O(1)空间的高效求解

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