每个k=1.. .n的k大小的所有子数组的最大和

Given an array of size n, for each k from 1 to n, find the maximum sum of contiguous subarray of size k.

给定一个大小为n的数组，对于从1到n的每个k，找到大小为k的连续子数组的最大和。

This problem has an obvious solution with time complexity O(N²) and O(1) space. Lua code:

这个问题有一个明显的解决方案，即时间复杂度为O(N2)和O(1)空间。Lua代码:

array = {7, 1, 3, 1, 4, 5, 1, 3, 6}
n = #array

function maxArray(k)
    ksum = 0
    for i = 1, k do
        ksum = ksum + array[i]
    end
    max_ksum = ksum
    for i = k + 1, n do
        add_index = i
        sub_index = i - k
        ksum = ksum + array[add_index] - array[sub_index]
        max_ksum = math.max(ksum, max_ksum)
    end
    return max_ksum
end

for k = 1, n do
    print(k, maxArray(k))
end

Is there any algorithm with lower time complexity? For example, O(N log N) + additional memory.

有没有时间复杂度较低的算法?例如，O(N log N) +额外的内存。

3 个解决方案

#1

I don't think there is a more efficient solution than O(N²) if you don't add any other constraint. In other words, there is no other way to decide you have found the maximum-sum subarray but to explore all the other subarrays.

我不认为有比O(N²)更有效的解决方案,如果你不添加任何其他限制。换句话说，除了探索所有其他的子数组之外，没有其他方法可以确定您已经找到了最大和子数组。

Thus the least-complex solution comprises O(N²/2) which is the overall number of contiguous subarrays of an array of given length N.

因此,最简单的解决方案由O(N²/ 2)的总数连续子序列的数组长度N。

Personally I would implement this with the dynamic programming approach. The idea is having a wedge of partial results, and use them to build the current sums of the subarrays (in place of computing the whole sum through). Anyhow this gives "only" a constant speedup, thus the complexity is O(N²/2)~O(N²).

就我个人而言，我将使用动态编程方法实现这一点。这个想法有一个部分结果的楔子，并使用它们来构建子数组的当前和(以计算整个计算的总和)。总之这给“仅仅”不断加速,因此,复杂度是O(N²/ 2)~ O(N²)。

The following is pseudocode - sorry for not speaking Lua

下面是伪代码——对不起，我没说Lua

// here we place temporary results, row by row alternating in 0 or 1
int[2][N] sum_array_buffer
// stores the start of the max subarray
int[N] max_subarray_start
// stores the value
int[N] max_subarray_value

array = {7, 1, 3, 1, 4, 5, 1, 3, 6}
// we initialize the buffer with the array (ideally 1-length subarrays)
sum_array_buffer[1] = array
// the length of subarrays - we can also start from 1 if considered
for k = 1 ; k <= (N); ++k:
    // the starting position fo the sub-array
    for j = 0; j < (N-k+1); ++j:
        sum_array_buffer[k%2][j] = sum_array_buffer[(k+1)%2][j] + array[j+k-1]
        if j == 0 || sum_array_buffer[k%2][j] > max_subarray_value[k]:
            max_subarray_value = sum_array_buffer[k%2][j]
            max_subarray_start[k] = j


for k = 1 ; k <= (N); ++k:
    print(k, max_subarray_value[k])

Graphycally:

式图形:

#2

We create a Dequeue, Qi of capacity k, that stores only useful elements of current window of k elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear of Qi is the smallest of current window.

我们创建一个Dequeue, Qi of capacity k，它只存储k元素当前窗口中有用的元素。如果元素在当前窗口中，并且比当前窗口中它左边的所有其他元素都大，那么该元素是有用的。我们逐一处理所有的数组元素，并维护Qi以包含当前窗口的有用元素，这些有用的元素按排序的顺序进行维护。气前的元素是最大的，气后的元素是当前窗口的最小的。

#3

-3

below process might help you

下面的过程可能会对您有所帮助

1) Pick first k elements and create a Self-Balancing Binary Search Tree (BST) of size k.

1)选择第一个k个元素，创建一个大小为k的自平衡二叉搜索树(BST)。

2) Run a loop for i = 0 to n – k

2)为i = 0到n - k运行一个循环。

…..a) Get the maximum element from the BST, and print it.

a)从BST获得最大元素，并打印出来。

…..b) Search for arr[i] in the BST and delete it from the BST.

在BST中搜索arr[i]并将其从BST中删除。

…..c) Insert arr[i+k] into the BST.

c)将arr[i+k]插入到BST中。

Time Complexity: Time Complexity of step 1 is O(kLogk). Time Complexity of steps 2(a), 2(b) and 2(c) is O(Logk). Since steps 2(a), 2(b) and 2(c) are in a loop that runs n-k+1 times, time complexity of the complete algorithm is O(kLogk + (n-k+1)*Logk) which can also be written as O(nLogk).

时间复杂度:第一步的时间复杂度是O(kLogk)。步骤2(a)、2(b)和2(c)的时间复杂度为O(Logk)。由于步骤2(a)、2(b)和2(c)在一个循环中运行n-k+1次，因此完整算法的时间复杂度为O(kLogk + (n-k+1)*Logk)，也可以写成O(nLogk)。

#1