至少长度l最大连续子总和 [英] Maximum Contiguous Subsequence Sum of At Least Length L

问题描述

因此​​，对于下面的数组，其中L = 3

So for the following array, where L = 3

-5 -1 2 -3 0 -3 3

至少长3所述的最好的可能的总和将是0，其中子序列是最后三要素（0，-3，3）

The best possible sum of at least length 3 would be 0, where the subsequence is the last three elements (0, -3, 3)

您如何计算比O（NL）更快的这笔钱用于任何阵列（有效O（N ^ 2）如果L == 0）的时间？

How can you calculate this sum for any array in faster than O(NL) (effectively O(N^2) if L==0) time?

推荐答案

我相信，你可以在O（n）的时间通过使用的Kadane's算法。

I believe that you can do this in O(n) time regardless of the choice of by using a modified version of Kadane's algorithm.

要看到这是如何工作的，让我们考虑的情况下，L = 0，在这种情况下，我们要找出原始序列的最大总和子数组。这可以通过Kadane的算法，一个聪明的动态规划的解决方案，它的工作原理如下得到解决。该想法是保持最大重量的重量的轨道子阵列之前和刚刚阵列中的每个位置之后结束。取其这些阵列的具有最大总和是具有最大总和的子阵列。让原始数组为A，并让在位置k结束的最大数额的阵列阵列M.然后Kadane的算法是这样的：

To see how this works, let's consider the case where L = 0. In that case, we want to find the maximum-sum subarray of the original sequence. This can be solved by Kadane's algorithm, a clever dynamic programming solution that works as follows. The idea is to keep track of the weight of the maximum-weight subarray ending just before and just after each position in the array. Whichever of these arrays has the largest sum is the subarray with the maximum total sum. Let the original array be A and let the array of maximum sums ending at position k be array M. Then Kadane's algorithm works like this:

• 设置M（0）= 0的任意结束之前的第一个数组项中不能有任何东西，因此它具有总和为零子阵。
• 对于每个阵列索引k，为了，将M设定为第（k + 1）= MAX（0，M（k）的+ A（k））的。这里的想法是，最好的子阵列结束之前该位置通过扩展从由单个元件的previous位置最好阵列形成的，或者通过丢弃阵列完全和刚采摘空子阵列这个位置之前。

一旦你填写此表男，你可以进行扫描，以找到最大值整体，它给你的最大权重子阵的重量。

Once you've filled in this table M, you can just scan it to find the maximum value overall, which gives you the weight of the maximum-weight subarray.

但是，我们如何适应这的情况下，L＆NE; 0？幸运的是，这是不是太糟糕了。看看复发的Kadane算法。的想法是，在每一个点，我们可以扩展该阵列由一个步骤，或者我们可以恢复为空数组。但是，如果我们对我们的子数组的大小的下限，我们可以认为这是不同的：长度至少我只是位置k之前结束的最大权重子阵+ 1或者由至少延伸长度最好阵列形成大号的结束只是位置k之前一个元素，或通过丢弃阵列，并采取了L型单元子阵的位置k前右结束。这给了我们Kadane算法的新版本，看起来像这样：

But how do we adapt this to the case where L ≠ 0? Fortunately, this isn't too bad. Look at the recurrence for Kadane's algorithm. The idea is that at each point we can either extend the array by one step, or we can reset back to the empty array. But if we have a lower bound on the size of our subarray, we can think of this differently: the maximum-weight subarray of length at least L ending just before position k + 1 is formed either by extending the best array of length at least L that ends just before position k by one element, or by discarding that array and taking the L element subarray that ends right before position k. This gives us a new version of Kadane's algorithm that looks like this:

• 集的M（L）等于所述阵列的第一L个元素的总和。
• 对于每个数组索引K＆GE; L时，按顺序，将M设定为第（k + 1）到M（k）的+ A（k）的（我们得到通过扩展阵列的值）的最大值和L个元件的刚位置k + 1之前的总和（在价值得到通过只是走过去的k个元素）。

如果我们运行这个，我们会在表中M值填补L到数组的长度。在这个范围内的最大值是那么对于长度至少含有L-子阵列的最大总和子阵列值

If we run this, we will fill in table M values from L to the length of the array. The maximum value in that range is then the maximum sum subarray value for subarrays of length at least L.

但是，这并不以线性时间运行！特别是，它运行在O（NL）中，由于计算的每次迭代具有看阵列的previous L个元素。然而，做一些额外的pre计算，我们可以删除这为O（n）。我们的想法是，我们可以按如下建立包含在O（n）的每个数组索引之前，L型单元的总和表的时间。首先，总结该阵列的第一L个元件，并存储为S（L）。这仅仅是位置L前的L个元件的总和现在，如果我们想只是指数L + 1之前得到的L个元件的总和，WR可以通过总结阵列的第一L个元件做秒，在加入下一数组元素，然后减去的第一数组元素。这可以在O（1）时间计算S（L + 1）= S（L）+ A（L）来完成 - A（0）。然后，我们可以使用类似的伎俩来计算S（L + 2）= S（L + 1）+ A（L + 1） - A（1）。更一般地，我们可以在部分和此表填写O（n）时间使用复发

But this doesn't run in linear time! In particular, it runs in O(nL), since each iteration of the computation has to look at the previous L elements of the array. However, by doing some extra pre computation, we can drop this to O(n). The idea is that we can build up a table containing the sums of the L element before each array index in O(n) time as follows. First, sum up the first L elements of the array and store that as S(L). This is the sum of the L elements just before position L. Now, if we want to get the sum of the L elements just before index L + 1, wr can do s by summing up the first L elements of the array, adding in the next array element, then subtracting out the very first array element. This can be done in O(1) time by computing S(L + 1) = S(L) + A(L) - A(0). We can then use a similar trick to compute S(L + 2) = S(L + 1) + A(L + 1) - A(1). More generally, we can fill in this table of partial sums in O(n) time using the recurrence

• S（L）= A（0）+ A（1）+ ... + A（L - 1）。
• S（L + K + 1）= S（L + K）+ A（L + K） - A（K）

这运行在O（n）时间。如果我们有这个表precomputed，我们就可以找到长度的最大权重的子数组至少L请使用此复发上面：

This runs in O(n) time. If we have this table precomputed, we can then find the maximum-weight subarray of length at least L by using this recurrence from above:

• M（L）= S（L）
• M（L + K + 1）= MAX（M（L + k）的+ A（L + k）的S（L + k））的

我们能够那么对面并购阵列扫描发现的最大值。这整个过程在O（n）的运行时间：我们需要O（n）的时间来计算S数组，O（n）的时间来计算中号数组，O（L）= O（n）的时间来找到最大值。它也需要O（L）的空间，因为我们需要存储的M和S阵列。

We can then just scan across the M array to find the maximum value. This whole process runs in O(n) time: we need O(n) time to compute the S array, O(n) time to compute M array, and O(L) = O(n) time to find the maximum value. It also takes O(L) space, since we need to store the M and S arrays.

但是，我们可以通过减少内存使用O（1）做的比这更好！关键是要注意到，在每一个点，我们并不需要对整个M和S阵列;刚刚过去的任期。因此，我们可以只保存M和S的最后一个值，从而只需要O（1）内存。在每一个点，我们也将继续跟踪，我们已经看到了并购数组中的最大值，所以我们并不需要按住m阵列我们在充满后，这则给出了如下的O（N） - 时间，O（1）空间算法求解的问题：

But we can do better than this by reducing the memory usage to O(1)! The trick is to notice that at each point we don't need the entire M and S arrays; just the last term. We can therefore just store the last value of M and S, which takes only O(1) memory. At each point, we will also keep track of the maximum value we've seen in the M array, so we don't need to hold the M array after we've filled it in. This then gives the following O(n)-time, O(1)-space algorithm for solving the problem:

• 设置S到最初L个数组元素的总和。
• 设置M =秒。
• 设置最佳= M
• 对k = L + 1到n时，数组的长度：
  • 设置S = S + A（K） - 第（k - L）
  • 设置M = MAX（M + A（K），S）
  • 设置最佳= MAX（最佳，M）
  • Set S to the sum of the first L array elements.
  • Set M = S.
  • Set Best = M
  • For k = L + 1 up to n, the length of the array:
    • Set S = S + A(k) - A(k - L)
    • Set M = max(M + A(k), S)
    • Set Best = max(Best, M)

    作为一个例子，这里是你与L-原来阵列上的痕迹通过算法= 3：

    As an example, here's a trace through the algorithm on your original array with 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。

    So the output is 0.

    或者，在不同的阵列具有L = 2：

    Or, on a different array with 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

    So the output is 15.

    希望这有助于！这是一个非常酷的问题！

    Hope this helps! This is a really cool problem!

    修改：我有一个 C ++实现这种算法可以，如果你有兴趣看一些实际的$ C $下的解决方案

    EDIT: I have a C++ implementation of this algorithm available if you're interested in looking at some actual code for the solution.

    这篇关于至少长度l最大连续子总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！