algorithm - 最小长度 L 的最大连续子序列和

Question

所以对于下面的数组，其中 L = 3

-5 -1 2 -3 0 -3 3

长度至少为 3 的最佳总和为 0，其中子序列是最后三个元素 (0, -3, 3)

你怎么能在比 O(NL)(如果 L==0 时有效 O(N^2))更快的时间内为任何数组计算这个总和？

Answer 1

我相信无论选择使用 Kadane's algorithm 的修改版本，您都可以在 O(n) 时间内完成此操作。 .

为了看看这是如何工作的，让我们考虑 L = 0 的情况。在这种情况下，我们想要找到原始序列的最大和子数组。这可以通过 Kadane 的算法来解决，一个聪明的 dynamic programming解决方案如下。这个想法是跟踪在数组中每个位置之前和之后结束的最大权重子数组的权重。这些数组中总和最大的就是总和最大的子数组。令原始数组为 A，并令在位置 k 处结束的最大和数组为数组 M。 然后 Kadane 的算法工作如下:

设置 M(0) = 0。在第一个数组条目之前结束的任何子数组都不能包含任何内容，因此它的总和为零。

对于每个数组索引 k，依次设置 ​​M(k + 1) = max(0, M(k) + A(k))。这里的想法是，在此位置之前结束的最佳子阵列要么是通过将最佳阵列从前一个位置扩展单个元素来形成的，要么通过完全丢弃该阵列并仅选择该位置之前的空子阵列来形成。

一旦你填写了这个表 M，你就可以扫描它以找到整体的最大值，这为你提供了最大权重子数组的权重。

但是我们如何适应 L ≠ 0 的情况呢？幸运的是，这还不算太糟糕。查看 Kadane 算法的循环。这个想法是在每一点我们可以将数组扩展一步，或者我们可以重置回空数组。但是，如果我们对子数组的大小有一个下限，我们可以以不同的方式思考:长度至少为 L 的最大权重子数组在位置 k + 1 之前结束，或者通过扩展长度至少为最佳的数组来形成L 在位置 k 之前结束一个元素，或者通过丢弃该数组并取在位置 k 之前结束的 L 元素子数组。这为我们提供了一个新版本的 Kadane 算法，如下所示:

设置 M(L) 等于数组的前 L 个元素的总和。

对于每个数组索引 k ≥ L，依次将 M(k + 1) 设置为 M(k) + A(k)(我们通过扩展数组得到的值)和之前的 L 个元素之和的最大值位置 k + 1(我们只取最后 k 个元素得到的值)。

如果我们运行它，我们将填充表 M 值，从 L 到数组的长度。该范围内的最大值是长度至少为 L 的子数组的最大和子数组值。

但这不是在线性时间内运行的!特别是，它在 O(nL) 中运行，因为计算的每次迭代都必须查看数组的前 L 个元素。但是，通过进行一些额外的预计算，我们可以将其降低到 O(n)。这个想法是我们可以在 O(n) 时间内构建一个包含每个数组索引之前的 L 元素总和的表，如下所示。首先，对数组的前 L 个元素求和并将其存储为 S(L)。这是位置 L 之前的 L 个元素的总和。 现在，如果我们想得到索引 L + 1 之前的 L 个元素的总和， wr 可以通过对数组的前 L 个元素求和来做 s，加上下一个数组元素，然后减去第一个数组元素。这可以通过计算 S(L + 1) = S(L) + A(L) - A(0) 在 O(1) 时间内完成。然后我们可以使用类似的技巧来计算 S(L + 2) = S(L + 1) + A(L + 1) - A(1)。更一般地，我们可以使用递归在 O(n) 时间内填写这个部分和的表

S(L) = A(0) + A(1) + ... + A(L - 1)。

S(L + k + 1) = S(L + k) + A(L + k) - A(k)。

这在 O(n) 时间内运行。如果我们预先计算了这个表，那么我们可以通过使用上面的循环来找到长度至少为 L 的最大权重子数组:

M(L) = S(L)

M(L + k + 1) = max(M(L + k) + A(L + k), S(L + k))

然后我们可以扫描 M 数组以找到最大值。整个过程在 O(n) 时间内运行:我们需要 O(n) 时间来计算 S 数组，O(n) 时间来计算 M 数组，以及 O(L) = O(n) 时间来找到最大值.它还需要 O(L) 空间，因为我们需要存储 M 和 S 数组。

但是我们可以通过将内存使用量减少到 O(1) 来做得更好!诀窍是注意在每个点我们不需要整个 M 和 S 数组；只是最后一个学期。因此，我们可以只存储 M 和 S 的最后一个值，这仅占用 O(1) 内存。在每个点，我们还将跟踪我们在 M 数组中看到的最大值，因此我们不需要在填充后保留 M 数组。这然后给出以下 O(n) -时间，O(1)-空间算法解决问题:

将 S 设置为前 L 个数组元素的总和。

设置 M = S。

设置最佳 = M

对于 k = L + 1 到 n，数组的长度:

设置 S = S + A(k) - A(k - L)

设置 M = max(M + A(k), S)

设置最佳 = max(Best, M)

输出最佳

举个例子，这里是在 L = 3 的原始数组上通过算法的跟踪:

        -5    -1    2      -3    0    -3    3
S                      -4     -2   -1    -6    0  
M                      -4     -2   -1    -4    0
Best                   -4     -2   -1    -1    0

所以输出为0。

或者，在 L = 2 的不同数组上:

        0   5    -3    -1    2   -4   -1    7   8
S              5     2    -4   1    -2   -5   6   15
M              5     2     1   3    -1   -2   6   15
Best           5     5     5   5     5    5   6   15

所以输出是15。

希望这可以帮助!这真是一个很酷的问题!

编辑 : 我有一个 C++ implementation 如果您有兴趣查看解决方案的一些实际代码，则可以使用此算法。