支持append和removeFirst操作的Kadane算法变体优化方案问询

你的场景是数组频繁做左端弹出、右端追加操作，每次更新后要快速计算任意大小的最大连续子数组和——每次跑O(n)的Kadane算法确实会在高频操作下累积不必要的开销，这里给两种针对性的优化思路：

一、前缀和+单调队列（分摊O(1)单次更新/查询） #

核心逻辑基于前缀和的性质：假设数组nums的前缀和数组为s（s[i]表示前i+1个元素的和），那么任意子数组nums[j..k]的和等于s[k] - s[j-1]。要最大化这个值，本质就是对每个s[k]，找到它之前最小的s[j-1]。

针对你的动态场景，可以维护两个队列：

• 一个前缀和队列：同步记录当前数组的前缀和序列——左端弹出元素时，弹出队列队首的前缀和；右端追加元素时，计算新的前缀和（队尾前缀和+新元素）并加入队尾。
• 一个单调递增队列：专门维护当前前缀和序列中的最小值候选。队首始终是当前最小的前缀和，确保后续计算时能快速拿到最优解。

每次数组更新后的操作步骤：

1. 移除首元素：
   • 如果单调队列的队首恰好是被移除的那个前缀和（也就是原数组的第一个前缀和），直接弹出队首
   • 弹出前缀和队列的队首
2. 追加新元素：
   • 计算新前缀和，加入前缀和队列
   • 从单调队列的队尾开始，把所有大于等于新前缀和的元素都删掉（这些元素不可能成为后续的最小前缀和候选），再把新前缀和加入队尾
3. 查询最大子数组和：
   • 遍历前缀和队列里的每个元素，计算「当前前缀和 - 单调队列队首」，取最大值
   • 同时还要单独考虑以当前数组第一个元素开头的所有子数组的最大和（避免前缀和全为负的情况），最后取所有候选里的最大值

这种方法的单次更新和查询均为分摊O(1)（每个元素最多入队、出队一次），空间复杂度是O(n)。

二、双向Kadane状态维护（适合固定长度滑动数组） #

如果你的数组长度是固定的（比如每次弹出首元素就追加一个新元素，数组长度不变），可以维护两组Kadane状态：

• forward[i]：以第i个元素结尾的最大连续子数组和
• backward[i]：以第i个元素开头的最大连续子数组和
• global_max：当前数组的最大子数组和

同时维护数组总和total_sum，以及正向、反向的局部最大值。当数组滑动时：

• 弹出首元素后，更新total_sum，并重新计算新数组的forward序列（从新的首元素开始）
• 追加新元素后，更新total_sum，并重新计算新数组的backward序列（到新的尾元素结束）
• 新的global_max可以取「原global_max（如果不包含被弹出的首元素）、新的正向最大值、新的反向最大值、跨中间的子数组和（forward[k] + backward[k+1]）」中的最大值

不过这种方法边界情况较多，比如原global_max刚好包含被弹出的首元素时，需要重新遍历计算，不如前缀和+单调队列稳定。

关键注意事项 #

当数组所有元素都是负数时，最大子数组和就是数组中最大的单个元素——这种情况一定要单独处理，比如维护一个全局的元素最大值变量，查询时和其他候选值做对比。

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