我相信您可以在O（n）时间内完成此操作，而不管选择使用修改版的Kadane算法。
为了了解其工作原理，让我们考虑L = 0的情况。在这种情况下，我们想找到原始序列的最大和子数组。这可以通过Kadane的算法来解决，该算法是一种聪明的动态编程解决方案，其工作原理如下。这个想法是要跟踪最大权重子数组的权重，该权重在数组中每个位置之前和之后结束。这些数组中总和最大的子数组是总和最大的子数组。设原始数组为A，以最大和的数组结尾于位置k为数组M。然后，Kadane的算法如下：
填写完表格M后，您可以对其进行扫描以找到整体的最大值，这为您提供了weight-weight子数组的权重。
但是，我们如何适应L≠0的情况？幸运的是，这还不错。查看Kadane算法的重复性。这个想法是，我们可以在每一点上将数组扩展一步，也可以将其重置为空数组。但是，如果我们对子数组的大小有一个下限，我们可以换个角度思考：长度至少为L的最大权重子数组恰好在位置k + 1之前结束，或者通过扩展长度的最佳数组来形成L在位置k之前一个元素结束，或者丢弃该数组并取在位置k之前结束的L元素子数组。这为我们提供了Kadane算法的新版本，如下所示：
如果运行此命令，则将填写从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）时间内填写此部分和表
这需要O（n）时间。如果我们已经对该表进行了预先计算，则可以使用上面的递归来找到长度至少为L的最大权重子数组：
然后，我们可以扫描整个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）-空间算法来解决此问题：
例如，这是对原始数组中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。
希望这可以帮助！这是一个很酷的问题！
602392714
清零编程群