关于使用最小前缀和解决子数组和问题的澄清

Question

我正在尝试理解竞争性编程中“最小前缀和”的概念，特别是对于涉及查找子数组的最大或最小和的问题。虽然我理解前缀和的概念，但使用最小前缀和进行优化的飞跃却让我无法理解。

主要困惑：

最小前缀和如何有助于有效地找到最佳子数组和？

有人可以用一个简单的例子来分解这种技术的应用吗？

Answer 1

当您从数组构造出前缀和数组时，您可以通过计算

psa[r] - psa[l - 1]

在 O(1) 时间内获得索引 [l, r] 之间的子数组中的元素之和。

现在，让我们考虑以索引

i

结尾的子数组的最大和。设该子数组的起点为

j

（其中j<= i). The sum of this subarray is given by

psa[i] - psa[j - 1]

。

i

是固定的，因此我们将

psa[i]

视为常数，只能移动

j

。由于我们要减去

psa[j - 1]

，所以我们想要最小化减去的量以最大化结果。因此，我们正在寻找所有 1

 的最小值 

psa[j - 1]<= j <= i (assuming 1-indexeding), i.e. the minimum prefix sum before the current index.

为了获得整个数组中的最大子数组和，我们对数组中的每个索引重复上述过程，时间和空间复杂度为 O(n)。