Consecutive numbers with sum equal to n
February 10, 2018
Protected: live classes
March 7, 2018

Maximum (or minimum) sum of subarray of size k

Given an array of n integers, find the sub-array of length k with maximum sum. For example,

Input Array: {6, 4, 3, 5, 1, 9, 2}    k:3
Output: 15 (sum of sub-array 5, 1, 9)


Solution:
The brute-force solution for this problem is to find sum of all the sub-arrays of length k, and return the maximum of all those sum.
A better solution is to use a sliding window where width of the sliding window is fixed to be of size k. There are two pointers, start and end, pointing to the first and last element of the current window. Sum of the first window is computed, and then both start and end are incremented by one position, now the sum of this window can be computed by just adding the new element and removing the outgoing element (previously start) from the previous window’s sum:

int maxSubarraySum(int *arr, int n, int k)
{
  if(k>n){ return -1;} // IMPOSSIBLE SITUATION
  int maxSum = 0;
  for(int i=0; i<k; i++)
    maxSum += arr[i];
  int start = 0;
  int end = k-1;
  int currentSum = maxSum;
  while(end<n) // MOVING THE WINDOW BY ONE POSITION
  {
    currentSum -= arr[start];
    start++;
    end++;
    currentSum += arr[end];
    if(currentSum > maxSum)
      maxSum = currentSum;
  }
  return maxSum;
}

This code takes O(n) time.

4 Comments

  1. kasper says:

    Hey Thanks for sharing your code but its not submitting in gfg

  2. kasper says:

    thanks!

  3. kasper says:

    correct solution is:
    int maximumSumSubarray(int K, vector &Arr , int N){
    int i=0,j=0;
    int M=1000000007;
    int globalMax=INT_MIN,currMax=0;
    for(j=0;j<K;j++) {
    currMax=currMax+Arr[j] ;

    }
    globalMax=max(globalMax,currMax);
    j=K-1;
    while(j<N-1){

    currMax=currMax-Arr[i];
    i++;
    j++;
    currMax+=Arr[j];
    globalMax=max(globalMax,currMax);
    }

    return globalMax%M;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *