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

Question

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

相关主题：

• 卡达内算法

Answer 1

一个有效的解是基于这样一个事实：一个大小为k的子数组（或窗口）的和可以在O(1)时间内用前面的大小为k的子数组（或窗口）的和来得到一个大小为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)