Maximum sum of all subarrays of size k for each k=1..n

Question

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

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

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.

Related topics:

• Kadane's algorithm

Answer 1

An Efficient Solution is based on the fact that sum of a subarray (or window) of size k can be obtained in O(1) time using the sum of previous subarray (or window) of size k. Except the first subarray of size k, for other subarrays, we compute sum by removing the first element of the last window and adding the last element of the current window.

here is the implementation of the same

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; 
 } 

Time Complexity : O(n) Auxiliary Space : O(1)

Source