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
Hey Thanks for sharing your code but its not submitting in gfg
but its running there
I tooo wondered how its not submiting?
thanks!
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;
}