最小连续子序列和最小长度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

我相信你可以在O(n)时间做到这一点,无论选择使用Kadane算法的修改版本.

要看到这是如何工作的,让我们考虑的情况下,L = 0.在这种情况下,我们要找出原始序列的最大总和子数组.这可以通过Kadane算法解决,这是一种巧妙的动态编程解决方案,其工作原理如下.我们的想法是跟踪在阵列中每个位置之前和之后结束的最大重量子阵列的权重.无论这些数组中具有最大总和的是具有最大总和的子阵列.让原始数组为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个元素得到的值).

如果我们运行它,我们将填充从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(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)
  • 设置最佳=最大(最佳,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++实现.