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

Question

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

这个问题有一个明显的解决方案，时间复杂度为 O(N²) 和 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

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

相关主题:

• Kadane's algorithm

Answer 1

一个有效的解决方案基于这样一个事实，即可以使用大小为 k 的前一个子数组(或窗口)的总和在 O(1) 时间内获得大小为 k 的子数组(或窗口)的总和。除了大小为 k 的第一个子数组，对于其他子数组，我们通过删除最后一个窗口的第一个元素并添加当前窗口的最后一个元素来计算和。

这里是相同的实现

int maxSum(int arr[], int n, int k) 
{ 
// k must be greater 
if (n < k) 
{ 
   cout << "Invalid"; 
   return -1; 
} 

// Compute sum of first window of size k 
int res = 0; 
for (int i=0; i<k; i++) 
   res += arr[i]; 

// Compute sums of remaining windows by 
// removing first element of previous 
// window and adding last element of  
// current window. 
int curr_sum = res; 
for (int i=k; i<n; i++) 
{ 
   curr_sum += arr[i] - arr[i-k]; 
   res = max(res, curr_sum); 
} 

return res; 
 } 

时间复杂度:O(n)辅助空间:O(1)

Source