Find Maximum Sum of a Subarray of size K.

Given an integer array of size n and a number k, find the maximum sum of a subarray of size k.

Example 1:

Input: arr[] = {2, 3, 5, 2, 9, 7, 1}  k = 3
Output: 18

Explanation: 
Sum of all possible subarrays of size 3
{2, 3, 5} = 2+3+5 = 10
{3, 5, 2} = 3+5+2 = 10
{5, 2, 9} = 5+2+9 = 16
{2, 9, 7} = 2+9+7 = 18
{9, 7, 1} = 9+7+1 = 17 
The maximum sum we get by adding the subarray {2, 9, 7} of size 3.

Example 2:

Input: arr[] = {5, -3, 2, 8, 4} k = 2
Output: 12

Explanation:
The maximum sum we get by adding the subarray {8, 4} of size 2

Approach 1: Brute Force

We can run two nested loops to calculate the sum of possible subarrays of the given size k and return the maximum of all sums. The time complexity of this approach will be O(n*k) where n is the number of elements in the array and k is the size of the subarray.

C++ Code for finding the maximum sum of a subarray of size k.

//C++ Code for maximum sum of subarray of size k 
#include<iostream>
using namespace std;

int maxSubarraySum(int arr[], int n, int k){

    int maxSum = INT_MIN;

    for(int i = 0; i < n-k; i++){
        int sum = 0;
        for(int j = i; j < i+k; j++){
            sum += arr[j];
        }
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}
int main(){
    int arr[] = {2, 3, 5, 2, 9, 7, 1};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    //size of subarray
    int k = 3;
    cout<<maxSubarraySum(arr, n, k);
}

Output:

Time Complexity: O(n*k)
Space Complexity: O(1)

Our brute force approach will work fine for a smaller value of k but as soon as the k value goes high our time complexity will also increase. We have to think of an optimized approach and we need to check that is there any repetitive work we are doing?

Approach 2: Fixed-size Sliding Window (Optimized approach).

If we observe carefully we notice that the time taken to calculate the sum of each subarray is O(k) but we can compute this calculation in O(1) time complexity for all the subarray except the first subarray of size k.

Here we are going to use the fixed-size sliding window concept to optimize our solution where the size of our Window is given as k. First, we are going to calculate the sum of our first subarray (window) of size k, and to get the sum of the next subarray we are going to add the next element in the current sum and remove the first element of the last window.

C++ Code for finding the maximum sum of a subarray of size k using the Sliding Window Approach.

//C++ Code for maximum sum of subarray of size k (optimized)

#include<iostream>
using namespace std;

//function to find maximum sum of subarray of size k
int maxSubarraySum(int arr[], int n, int k){
    //variable to store maxSum
    int maxSum = INT_MIN;
    //variable to calculate window size
    int i = 0, j = 0;
    int sum = 0;
    
    while(j < n){
        sum = sum + arr[j];
        //Window size is less than k
        if(j-i+1 < k){
            j++;
        }
        /*we get one of the possible answer, store it
        and remove the calculation of ith element and 
        slide the window by one unit*/
        else if(j-i+1 == k){
            maxSum = max(maxSum, sum);
            sum = sum - arr[i];
            i++;
            j++;
        }
    }
    return maxSum;
}
int main(){
    int arr[] = {2, 3, 5, 2, 9, 7, 1};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    //size of subarray
    int k = 3;
    cout<<maxSubarraySum(arr, n, k);
}

Output:

Time Complexity: O(n)
Space Complexity: O(1)

Find Maximum Sum of a Subarray of size K.

No comments:

Post a Comment