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[2] + arr[3] gives the maximum sum (30+50 = 80)

Naive Approach

We could run two loops from i=0 to n-k and j=i to i+k-1, where n is the size of the 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 the 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(n²). 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]

Find maximum sum of contiguous subarray solution

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