我相信您可以在O（n）时间内完成此操作，而不管选择使用修改版的Kadane算法。

为了了解其工作原理，让我们考虑L =
0的情况。在这种情况下，我们想找到原始序列的最大和子数组。这可以通过Kadane的算法来解决，该算法是一种聪明的动态编程解决方案，其工作原理如下。这个想法是要跟踪最大权重子数组的权重，该权重在数组中每个位置之前和之后结束。这些数组中总和最大的子数组是总和最大的子数组。设原始数组为A，以最大和的数组结尾于位置k为数组M。然后，Kadane的算法如下：

• 设置M（0）=0。任何在第一个数组条目之前结束的子数组都不能包含任何内容，因此它的总和为零。
• 对于每个数组索引k，依次设置M（k + 1）= max（0，M（k）+ A（k））。这里的想法是，最好的子数组在此位置之前结束，或者通过将最佳数组从先前位置扩展一个元素来形成，或者通过完全丢弃该数组并仅在该位置之前选择一个空子数组来形成。

填写完表格M后，您可以对其进行扫描以找到整体的最大值，这为您提供了weight-weight子数组的权重。

但是，我们如何适应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个元素而获得的值）。

如果运行此命令，则将填写从L到数组长度的表M值。然后，该范围内的最大值是长度至少为L的子数组的最大和子数组值。

但这不是线性时间！特别是，它以O（nL）运行，因为计算的每次迭代都必须查看数组的前L个元素。但是，通过执行一些额外的预计算，我们可以将其降至O（n）。想法是，我们可以建立一个包含O（n）时间中每个数组索引之前的L元素之和的表，如下所示。首先，对数组的前L个元素求和，并将其存储为S（L）。这是位置L之前的L个元素的总和。现在，如果我们要获取索引L
+ 1之前的L个元素的总和，则wr可以通过对数组的前L个元素求和，然后加下一个数组元素，然后减去第一个数组元素。这可以通过计算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（长）= S（长）
• M（L + k + 1）=最大值（M（L + k）+ A（L + k），S（L + k））

然后，我们可以扫描整个M数组以找到最大值。这整个过程需要O（n）时间：我们需要O（n）时间来计算S数组，需要O（n）时间来计算M数组，并且O（L）=
O（n）时间来找到最大值。由于我们需要存储M和S数组，因此它也占用O（L）空间。

但是我们可以通过将内存使用量减少到O（1）来做得更好！诀窍是要注意，在每个点上我们都不需要整个M和S数组。只是最后一个学期。因此，我们可以只存储M和S的最后一个值，该值仅占用O（1）内存。在每个点上，我们还将跟踪在M数组中看到的最大值，因此我们在填充完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）
  • 设置最佳=最大值（最佳，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
++实现 。