问题描述
因此对于以下数组，其中 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)(如果 L==0)的时间更快地计算任何数组的总和?
How can you calculate this sum for any array in faster than O(NL) (effectively O(N^2) if L==0) time?
推荐答案
我相信无论选择使用Kadane 算法.
为了了解它是如何工作的，让我们考虑 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)).这里的想法是，在此位置之前结束的最佳子数组要么是通过将最佳数组从前一个位置扩展一个元素来形成的，要么通过完全丢弃该数组并仅选择该位置之前的空子数组来形成.
一旦你填写了这个表 M，你就可以扫描它以找到整体的最大值，这给你最大权重子数组的权重.
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 ≠0?幸运的是，这还不算太糟糕.查看 Kadane 算法的循环.这个想法是在每一点我们可以将数组扩展一步，或者我们可以重置回空数组.但是，如果我们对子数组的大小有一个下限，我们可以不同地思考:长度至少为 L 的最大权重子数组在位置 k + 1 之前结束，或者通过扩展长度至少为最佳的数组来形成L 在位置 k 之前结束一个元素，或者通过丢弃该数组并取在位置 k 之前结束的 L 元素子数组.这为我们提供了一个新版本的 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 ≥L，按顺序，将 M(k + 1) 设置为 M(k) + A(k)(我们通过扩展数组得到的值)和位置 k + 1 之前的 L 个元素之和的最大值(即我们只取最后 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) 中运行，因为计算的每次迭代都必须查看数组的前 L 个元素.但是，通过进行一些额外的预计算，我们可以将其降为 O(n).这个想法是我们可以在 O(n) 时间内构建一个包含每个数组索引之前的 L 元素总和的表，如下所示.首先，将数组的前 L 个元素相加并将其存储为 S(L).这是位置 L 之前的 L 个元素的总和. 现在，如果我们想获得索引 L + 1 之前的 L 个元素的总和，wr 可以通过对数组的前 L 个元素求和来做 s，添加下一个数组元素，然后减去第一个数组元素.这可以通过计算 S(L + 1) = S(L) + A(L) - A(0) 在 O(1) 时间内完成.然后我们可以使用类似的技巧来计算 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) 时间内运行.如果我们预先计算了这个表，我们就可以使用上面的循环找到长度至少为 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))
然后我们可以扫描 M 数组以找到最大值.整个过程在 O(n) 时间内运行:我们需要 O(n) 时间来计算 S 数组，O(n) 时间来计算 M 数组，以及 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 数组中看到的最大值，因此我们不需要在填充后保留 M 数组.这然后给出以下 O(n)-time，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 = S.
- 设置最佳 = M
- 对于 k = L + 1 到 n，数组的长度:
- 设置 S = S + A(k) - A(k - L)
- 设置 M = max(M + A(k), S)
- 设置最佳 = 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.
或者，在 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.
希望这有帮助！这是一个很酷的问题！
Hope this helps! This is a really cool problem!
编辑:我有一个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 的最大连续子序列和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！