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

below process might help you

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

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

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

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

…..c) Insert arr[i+k] into the 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).

Answer 2

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

Answer 3

int maxCrossingSum(int arr[], int l, int m, int h) 
{ 
    // Include elements on left of mid. 
    int sum = 0; 
    int left_sum = INT_MIN; 
    for (int i = m; i >= l; i--) 
    { 
        sum = sum + arr[i]; 
        if (sum > left_sum) 
          left_sum = sum; 
    } 

    // Include elements on right of mid 
    sum = 0; 
    int right_sum = INT_MIN; 
    for (int i = m+1; i <= h; i++) 
    { 
        sum = sum + arr[i]; 
        if (sum > right_sum) 
          right_sum = sum; 
    } 

    // Return sum of elements on left and right of mid 
    return left_sum + right_sum; 
} 

// Returns sum of maxium sum subarray in aa[l..h] 
int maxSubArraySum(int arr[], int l, int h) 
{ 
   // Base Case: Only one element 
   if (l == h) 
     return arr[l]; 

   // Find middle point 
   int m = (l + h)/2; 

   /* Return maximum of following three possible cases 
      a) Maximum subarray sum in left half 
      b) Maximum subarray sum in right half 
      c) Maximum subarray sum such that the subarray crosses the midpoint */
   return max(maxSubArraySum(arr, l, m), 
              maxSubArraySum(arr, m+1, h), 
              maxCrossingSum(arr, l, m, h)); 
} 

Explanation

Using Divide and Conquer approach, we can find the maximum subarray sum in O(nLogn) time. Following is the Divide and Conquer algorithm.

1) Divide the given array in two halves

2) Return the maximum of following three

….a) Maximum subarray sum in left half (Make a recursive call)

….b) Maximum subarray sum in right half (Make a recursive call)

---

source

Answer 4

    The above question can be solved by O(n).
    Please try this algorithm.
    lets say k=3.
array = {7, 1, 3, 1, 4, 5, 1, 3, 6}
    maxsum=0.
    1)We start with adding 7+1+3 and store sum=11.since sum >maxsum.maxsum=11.
    2)Now since size of k=3,next continuous array is 1+3+1.so how we get this sum??
    remove 7 from sum and add 1 to sum.so now sum is 5.Check if sum>maxsum.
    3)Similarly do for other elements as well.This loop will run until (n-1).``

Please find the code here

 class Program
    {
        static void Main(string[] args)
        {
            int sum=0;
            int max=0;
            int size=9;
           string input="7, 1, 3, 1, 4, 5, 1, 3, 6";
           string[] values=input.Split(',');
           int length=values.Length;
           int k=size-1;
           for(int i=0;i<=k;i++)
           {
             sum=sum+int.Parse(values[i]);
             max=sum;
           }
           for(int j=0;k<length-1;j++)
           {
               ++k;
            sum=(sum-int.Parse(values[j]))+int.Parse(values[k]);
            if(sum>max)
            max=sum;
           }
           Console.WriteLine(max);
        }
    }

Answer 5

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.

Thus the least-complex solution comprises O(N²/2) which is the overall number of contiguous subarrays of an array of given length 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²).

The following is pseudocode - sorry for not speaking 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:

Answer 6

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.

Answer 7

The problem can be reduced to min-sum convultion, see section 2.4 (MCSP) in https://core.ac.uk/download/pdf/84869149.pdf. Therefore, currently the best complexity you can expect is probably O(n^2/polylog(n)).