algorithm - 如何找到具有最大和的最小连续子数组？

Question

Kadane 的算法可以找到我们最大的连续子数组和以及开始和结束索引，但连续子数组不一定总是最小的。例如：10 5 -12 7 -10 20 30 -10 50 60。整个数组的累积和是 150。最后 5 个元素的累积和也是 150。你将如何修改算法以找到最小的子数组？

Answer 1

我们可以O(n)通过两次遍历来解决这个问题。在第一次遍历中，使用 Kadane 算法找到最大和，S。对于第二次遍历，在https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/solution/有一个很好的描述来维护数组前缀的索引的两端队列总和，以便能够保持单调递增列表的索引prefix_left，我们可以与prefix_right（当前索引）进行比较减去S. 我们正在寻找最小的r - l这样的prefixes[l] ≤ prefixes[r] - S。而prefixes[l] ≥ prefixes[r], 向左弹出。然后prefixes[l] ≤ prefixes[r] - S更新解决方案并弹出左侧（因为任何更大的r索引只会针对相同的 生成更大的间隔l）。附加y到队列。