数组区间和问题——前缀和与 Kadane 算法

一、它们解决什么问题算法解决的问题典型题目前缀和快速求任意子数组的和303. 区域和检索Kadane求最大子数组和53. 最大子数组和一个关注“怎么快速求和”一个关注“和最大是多少”。二、前缀和定义prefix[i]表示前i个元素的和prefix[0] 0。子数组[l, r]的和 prefix[r1] - prefix[l]。代码模板int[] prefix new int[n 1]; for (int i 0; i n; i) { prefix[i 1] prefix[i] nums[i]; } // 子数组 [i, j] 的和 prefix[j1] - prefix[i]手动模拟nums [1,2,3,4]iprefix[i]00112336410子数组[1,3]的和 prefix[4] - prefix[1] 10 - 1 9优点O(1) 时间求任意子数组和适合多次查询。缺点需要额外 O(n) 空间。三、Kadane 算法核心思想从左往右遍历维护sum到当前位置为止包含当前元素的最大子数组和max全局最大和递推if (sum 0) sum nums[i]; else sum nums[i]; max Math.max(max, sum);代码int sum nums[0]; int max nums[0]; for (int i 1; i nums.length; i) { if (sum 0) sum nums[i]; else sum nums[i]; max Math.max(max, sum); } return max;手动模拟nums [-2,1,-3,4,-1,2,1,-5,4]inums[i]之前 sum新 summax0-2--2-211-2 ≤0112-31 0-2134-2 ≤0444-14 034523 055615 0667-56 016841 056结果 6优点O(n) 时间O(1) 空间一次遍历。缺点只适用于“最大子数组和”这类特定问题。四、两者对比对比前缀和Kadane目的快速求任意子数组和求最大子数组和核心prefix[r1] - prefix[l]sum max(nums[i], sumnums[i])时间复杂度预处理 O(n)查询 O(1)O(n)空间复杂度O(n)O(1)典型题目303、336453五、总结需要多次查询子数组和→ 前缀和需要找最大子数组和→ Kadane需要在长度限制下找最小正和→ 暴力枚举 前缀和优化两个不是替代关系各有各的用处。