至少长度L的最大连续子序列和。

So for the following array, where L = 3

对于下面的数组，L = 3。

-5 -1 2 -3 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)

最小长度为3的最佳组合是0，其中子序列是最后三个元素(0，- 3,3)

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

你怎么能计算任何数组求和的速度比O(NL)(有效O(N ^ 2)如果L = = 0)时间?

5 个解决方案

#1

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.

我相信你可以在O(n)时间内做这个，而不考虑使用修改后的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:

为了了解它是如何工作的，让我们考虑一下L = 0的情况。在这种情况下，我们希望找到原始序列的最大和子数组。这可以通过Kadane的算法来解决，这是一个很聪明的动态规划解决方案，它的工作原理如下。这个想法是在数组的每个位置之前和之后跟踪最大权重的子数组的权重。其中，这些数组中最大的一个是子数组，它的总数是最大的。让原始的数组为A，让数组的最大值以k为数组结束，然后Kadane的算法是这样的:

• Set M(0) = 0. Any subarray ending just before the first array entry can't have anything in it, so it has sum zero.
• 集M(0)= 0。任何子数组在第一个数组项之前结束都不能有任何值，所以它是和0。
• For each array index k, in order, set M(k + 1) = max(0, M(k) + A(k)). The idea here is that the best subarray ending just before this position is either formed by extending the best array from the previous position by a single element, or by discarding that array entirely and just picking the empty subarray before this position.
• 对于每个数组索引k，按顺序，设置M(k + 1) = max(0, M(k) + A(k))。这里的想法是，最好的子数组在这个位置之前结束，要么是通过一个元素将最好的数组从之前的位置扩展出来，要么是完全丢弃那个数组，然后在这个位置之前选择空的子数组。

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.

一旦你填满了这张表M，你就可以扫描它来找到最大的值，这就给了你最大的子数组的权重。

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:

但是我们如何使它适应L ?幸运的是，这还不算太糟。看看Kadane算法的递归式。我们的想法是，在每个点上，我们可以通过一个步骤来扩展数组，或者我们可以重新设置为空数组。但是如果我们有一个下界的子数组的大小,我们可以认为这个不同:最大重量的子数组的长度至少L结束前位置k + 1是通过扩展形成最好的数组的长度至少L结束前位置k的一个元素,或丢弃,数组和L元素子数组结束之前位置k。这给了我们一个新版本的Kadane这样的算法:

• Set M(L) equal to the sum of the first L elements of the array.
• 集合M(L)等于数组的第一个L元素的和。
• For each array index k ≥ L, in order, set M(k + 1) to the maximum of M(k) + A(k) (the value we get by extending the array) and the sum of the L elements just before position k + 1 (the value we get by just taking the last k elements).
• 为每个数组索引k≥L,M(k + 1)设置为最大M(k)+(k)(我们得到的值通过扩展数组)和L的和元素位置前k + 1(只是把我们得到的价值最后k元素)。

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.

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

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

但这不是在线性时间内运行的!特别是，它在O(nL)中运行，因为计算的每个迭代都必须查看数组的前一个L元素。但是，通过做一些额外的预计算，我们可以将其降至O(n)。我们的想法是，我们可以在O(n)时间的每个数组索引之前建立一个包含L元素和的表。首先，对数组的第一个L元素求和并将其存储为S(L)。这是之和L元素位置前L .现在,如果我们想要的和L元素之前指数L + 1,或者说是可以做年代总结第一个数组的元素,添加在下一个数组元素,然后减去第一个数组元素。通过计算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) = A(0) + A(1) +…+(L - 1)。
• S(L + k + 1) = S(L + k) + A(L + k) - A(k).
• S(L + k + 1) = S(L + k) + A(L + k) - A(k)

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:

这是在O(n)时间内运行的。如果我们预先计算了这个表，我们就可以通过上面的这个递归来找到最小长度的最大子数组。

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

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.

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

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:

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

• Set S to the sum of the first L array elements.
• 集合S到第一个L数组元素的和。
• Set M = S.
• M = S。
• Set Best = M
• 设置最佳= M
• For k = L + 1 up to n, the length of the array:
  • Set S = S + A(k) - A(k - L)
  • 集合S = S + A(k) - A(k - L)
  • Set M = max(M + A(k), S)
  • 集合M = max(M + A(k) S)
  • Set Best = max(Best, M)
  • 最好= max(最好，M)
• 对于k = L + 1到n，数组的长度:S = S + A(k) - A(k - L)集M = max(M + A(k)， S) = max(Best, M)
• Output Best
• 输出最好

As an example, here's a trace through the algorithm on your original array with L = 3:

举个例子，这是在原始数组中使用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

So the output is 0.

所以输出是0。

Or, on a different array with L = 2:

或者，在另一个数组中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

So the output is 15.

所以输出是15。

Hope this helps! This is a really cool problem!

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

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

编辑:如果您有兴趣查看解决方案的一些实际代码，我有一个c++实现。

#2

This is possible to do using dynamic programming in O(n).

这可以在O(n)中使用动态编程。

1.) Store the partial sums up to i for each index i in the array

1)。将对数组中每个索引i的部分汇总值存储起来。

2.) Store the index of the minimum sum up to i

2)。将最小值的索引存储到i。

3.) Store the maximum up to i for each index i in the array, which is the partial sum up to i minus the partial sum with the index determined in step 2, which is Min(Sum(k)) k <=i keeping in mind the constraint that the sub sequence must be at least of length L.

3)。商店的最大我为每个索引的数组,这是我减去的部分总结部分和索引确定在步骤2中,这是最小值(sum(k))k < =我记住的约束子序列的长度必须至少。

All of this can be done in O(n) in one loop.

所有这些都可以在一个循环中完成。

Now that you have the maximum sums up to i for each index i in the array you can determine the maximum sum of the contiguous sub sequence and the end index of that sub sequence. When you have the end index, you can just walk backwards until you have reached that maximum sum. Both of these operations are also O(n).

现在，对于数组中的每个索引i，你都有了最大的总结，你可以确定连续子序列的最大和和子序列的结束索引。当你有了最终指数，你可以往回走，直到你达到那个最大值。这两种操作都是O(n)。

Sample implementation in C#:

在c#示例实现:

int [] values = {-5, -1, 2, -3, 0, -3, 3};
int L = 3;

int[] sumUpTo = new int [values.Length];
int[] minUpTo = new int[values.Length];
int[] maxUpTo = new int[values.Length];

for (int i = 0; i < values.Length; i++)
{
    sumUpTo[i] = values[i];
    minUpTo[i] = i;
    if (i > 0)
    {
        sumUpTo[i] += sumUpTo[i - 1];
        minUpTo[i] = sumUpTo[i] < sumUpTo[i - 1] ? i : minUpTo[i - 1];
    }
    maxUpTo[i] = sumUpTo[i] - ((i >= L && sumUpTo[minUpTo[i - L]] < 0) ? sumUpTo[minUpTo[i - L]] : 0);
}


int maxSum = int.MinValue;
int endIndex = -1;

for (int i = L-1 ; i < values.Length; i++)
    if(maxUpTo[i] > maxSum)
    {
        endIndex = i;
        maxSum = maxUpTo[i];
    }

//Now walk backwards from maxIndex until we have reached maxSum
int startIndex = endIndex;
int currentSum = values[startIndex];

while (currentSum != maxSum || (endIndex - startIndex < L-1))
{
    startIndex--;
    currentSum += values[startIndex];

}

Console.WriteLine("value of maximum sub sequence = {0}, element indexes {1} to {2}", maxSum, startIndex, endIndex);

#3

Here is the JAVA version : 

Note : Credit goes to @templatetypedef. That explanation is awesome.


 public static int max_sum_in_subarray_of_minimum_length(int [] array, int min_length){

    int running_sum=0, max_sum_up_to_here=0, max_sum=0;

    int begin=0, end=0, max_start=0;

  /* max_sum_up_here = sum of all elements in array up to length L */

    for(int i=0;i<min_length;i++){

        max_sum_up_to_here+=array[i];
    }

  /* running sum and max sum = max_sum_up_here */

    running_sum = max_sum_up_to_here;
    max_sum= running_sum;

  /* Iterate through all elements starting from L i.e minimum length */

    for(int i=min_length;i<array.length;i++){

  /* min_sum_up_to_here = min_sum_up_to_here +
   next element in array - (i-L)th element in array */    

        max_sum_up_to_here+=array[i]-array[i-min_length];

  /* if running_sum + next element in array > max_sum_up_to here then 
         running_sum = running_sum + next element in array 
     else running_sum = max_sum_up_to_here */

        if( (running_sum+array[i]) > max_sum_up_to_here ){


            running_sum = running_sum+array[i];
            max_start = i-min_length+1;

         }else{

            running_sum= max_sum_up_to_here;
        }

     /* if running sum > max_sum then max_sum = running sum */

        if( max_sum < running_sum ){


            max_sum = running_sum;

            begin =max_start;

            end=i;

        }

    }

     /* max_sum gives sum of contiguous sub array of length L and begin and end gives indexes of the sub array*/  

    return max_sum;
}

#4

Useless cases and definitions, etc. My solution is the natural one. First of all, keep this in mind, we are looking for the maximum sum of a contiguous fragment of an array of integers, that fragment has more than or exactly L elements. Let's name A the initial array. For the same reasons like in Kadane's algorithm, we consider an auxiliary array, REZ, having N elements, like A, REZ[i] means the maximum sum of a contiguous fragment of A, containing at least L elements and ending exactly at the i-th position. Of course, REZ[1], RZ[2], REZ[L-1] are all equal with a ZERO or -INFINITY value. REZ[L]=A[1]+A[2]+...+A[L]. For the rest of the values in REZ, from i growing from L+1 to N, to calculate REZ[i] we have to choose the maximum between two cases:

无用的案例和定义，等等。我的解决方案是自然的。首先，记住这一点，我们正在寻找一个整数数组中一个连续的片段的最大和，这个片段包含了更多的L元素。让我们命名一个初始数组。基于同样的原因，在Kadane的算法中，我们考虑一个辅助数组，REZ，有N个元素，像A, REZ是指一个连续碎片的最大和，包含至少L元素，并以第i个位置结束。当然，雷兹[1]，RZ[2]， REZ[L-1]都等于0或-∞的值。资源文件格式[L]=[1]+[2]+……+一个[L]。在我从L+1到N的过程中，我们需要在两种情况下选择最大值:

1. a fragment of exactly L values and containing A[i]
2. 一个恰好L值的片段，包含一个[i]
3. a fragment having more than L values and containing A[i]
4. 具有大于L值并包含[i]的片段

The result for the first case can be calculated instantly with the partial sum array (S[i]=A[1]+A[2]+...+A[i]), S[i]-S[i-L]. The result for the second case is REZ[i-1]+A[i]. So,

第一种情况的结果可以用部分和数组立即计算出来(S[i]=A[1]+A[2]+ A[i])， S[i]-S[i- l]。第二个case的结果是REZ[i-1]+A[i]。所以,

• REZ[i]=-INFINITY, if 1<=i<=L-1
• 资源文件格式[我]=无穷大,如果1 < =我< = l - 1
• REZ[i]=S[i], if i=L
• 资源文件格式[我]=[我],如果我= L
• REZ[i]=max(S[i]-S[i-L], REZ[i-1]+A[i]), if i>L.
• 资源文件格式[我]= max(S - S(我),(我)资源文件格式(张)+[我]),如果我> L。

After REZ was built we have to calculate its maximum value. Let's consider the following example:

在雷兹建立之后，我们必须计算它的最大值。让我们考虑下面的例子:

N=7

N = 7

A -5 -1 2 -3 0 -3 3

A -5 -1 - 2 -3 0 -3 3。

L=3

L = 3

S -5 -6 -4 -7 -7 -10 -7

S -5 -6 -4 -7 -7 -10 -7。

REZ: -INF -INF -4

资源文件格式:负负4

REZ[4]=max(S[4]-S[4-3],REZ[3]+A[4])=max(-2, -7)=-2

资源文件格式[4]= max(S[4]- S(4 - 3),兹[3]+[4])= max(2、7)= 2

REZ: -INF -INF -4 -2

-INF -INF -4 -2。

REZ[5]=max(S[5]-S[5-3],REZ[4]+A[5])=max(-1,-2)=-1

资源文件格式[5]= max(S[5]- S(5 - 3),兹[4]+[5])= max(1、2)= 1

REZ: -INF -INF -4 -2 -1

-INF -INF -4 -2 -1。

REZ[6]=max(S[6]-S[6-3], REZ[5]+A[6])=max(-6,-4)=-4

资源文件格式[6]= max(S[6]- S[6],兹[5]+[6])= max(6,4)= 4

REZ: -INF -INF -4 -2 -1 -4

-INF -INF -4 -2 -1 -4。

REZ[7]=max(S[7]-S[7-3],REZ[6]+A[7])=max(0,-1)= 0

资源文件格式[7]= max(S[7]- S[7],兹[6]+[7])= max(0,1)= 0

REZ: -INF -INF -4 -2 -1 -4 0

-INF -INF -4 -2 -1 -4 0。

The maximum value in REZ is 0 and this is the answer for the whole problem.

REZ的最大值是0，这是整个问题的答案。

I hope my English is good enough. I am searching for a solution for a similar problem, when the result must have at most L consecutive elements. When I realised that the methods described above were actually for solutions having at least L elements, I was quite disappointed.

我希望我的英语足够好。我正在寻找一个类似问题的解决方案，当结果必须是大多数L连续的元素。当我意识到上面描述的方法实际上是针对至少有L元素的解决方案时，我非常失望。

#5

Below is my Java implementation.

下面是我的Java实现。

public static int maxSumSubsequenceGivenLength(int[] array, int l) {

    if (null == array || array.length < l) {
        return -1;
    }

    int previousSequenceSum = 0;

    for (int i = 0; i < l; i++) {
        previousSequenceSum += array[i];
    }

    int maxSum = previousSequenceSum;
    int currentSum = 0;
    int startIndexFinal = 0;
    int endIndexFinal = l - 1;

    for (int i = l; i < array.length; i++) {
        currentSum = previousSequenceSum + array[i] - array[i - l];
        if (currentSum > maxSum) {
            maxSum = currentSum;
            endIndexFinal = i;
            startIndexFinal = i - l + 1;
        }
        previousSequenceSum = currentSum;
    }

    System.out.println("start index:" + startIndexFinal + " end index: " + endIndexFinal);
    return maxSum;
}