# Find maximum sum of contiguous subarray of size k [Sliding Window]

Problem

You’re given an array of size N. You’ve to find the maximum sum obtained from a contiguous subarray of size k of the given array, where k <= N.

Example 1:

Input: arr[] = {10, 40, 30, 50}, k =2
Output: 80
Explanation: Subarray arr[2,3] ie arr + arr gives the maximum sum (30+50 = 80)
###### Naive Approach

We could run two loops from i=0, n-k and j=i, i+k-1, where n is the size of array. And we keep updating the maximum sum value

###### Pseudocode
1. for i=0 to n-k:
2.   currSum = 0;
3.   for j=i to i+k-1:
4.     currSum += arr[j];
5.   maxSum = max(maxSum, currSum)
6. return maxSum       

Code Implementation

//
//  main.cpp
//  Subarray with max sum
//
//  Created by Himanshu on 18/09/21.
//

#include <iostream>
#include <climits>
using namespace std;
const int N = 7;

int solve (int A[], int k) {

int maxSum = INT_MIN;
for (int i=0; i<=N-k; i++) {
int currSum = 0;
for (int j=i; j<=(i+k-1); j++) {
currSum += A[j];
}
maxSum = max(maxSum, currSum);
}

return maxSum;
}

int main() {
int A[N] = {5, 3, 4, 6, 8, 11, 20};
int k = 7;

cout<<"Maximum subset sum: "<<solve(A, k)<<endl;

k = 4;
cout<<"Maximum subset sum: "<<solve(A, k)<<endl;

}


Output:

Maximum subset sum: 57
Maximum subset sum: 45

Time complexity of above solution is O(N*k)

###### Sliding window technique

The Sliding window is a problem-solving technique for problems that involve finding subarrays of an array with given sum or minimum/maximum sum. These problems could be solved by brute force approach in O(n2). Using the ‘sliding window’ technique, we can reduce the time complexity to O(n).

A sliding window is a contiguous sub-list that runs over an underlying collection i.e., if you have an array like

[5, 3, 4, 6, 8, 11, 20]

A sliding window of size 3 would be like

[5, 3, 4], 6, 8, 11, 20
5, [3, 4, 6], 8, 11, 20
5, 3, [4, 6, 8], 11, 20
5, 3, 4, [6, 8, 11], 20
5, 3, 4, 6, [8, 11, 20]
###### Pseudocode
SlidingWindow(A, k)
1. currSum = 0, maxSum = INT_MIN
2. for i=0 to k:
3.   currSum += A[i]
4. maxSum = max(currSum, maxSum)
5. for i=k to n-1:
6.     currSum += arr[i] - arr[i-k]
7.     maxSum = max(maxSum, currSum)
8. return maxSum       

Code Implementation

//
//  main.cpp
//  Sliding Window
//
//  Created by Himanshu on 18/09/21.
//

#include <iostream>
#include <climits>
using namespace std;
const int N = 7;

int solve (int A[], int k) {

int maxSum = INT_MIN, currSum = 0;

for (int i=0; i<k; i++) {
currSum += A[i];
}

maxSum = max(maxSum, currSum);
for (int i=k; i<N; i++) {
currSum += A[i] - A[i-k];
maxSum = max(maxSum, currSum);
}

return maxSum;
}

int main() {
int A[N] = {5, 3, 4, 6, 8, 11, 20};
int k = 7;

cout<<"Maximum subset sum: "<<solve(A, k)<<endl;

k = 4;
cout<<"Maximum subset sum: "<<solve(A, k)<<endl;

}


Output:

Maximum subset sum: 57
Maximum subset sum: 45

Time complexity of the above solution is O(N)

Here’s a working example: Ideone