Maximum Sum Of K Size Subarray

Table Of Contents

Problem Statement:
Solution:
Code:
Time Complexity:
Space Complexity:

Problem Statement:

Given an array, find the maximum sum of any contiguous subarray of size “k” in it.

Example 1:

Input: arr: [2, 6, -9, 7, -1, 5, 4], k: 3
Output: 11
Explanation: The subarray (7, -1, 5) of size 3 gives the maximum sum of 11.

Example 2:

Input: arr: [5, 2, -4, 9, -8, 3, -1, 5], k: 5
Output: 8

Solution:

Let’s brief the problem first. So, the problem says us to find the sum of each contiguous subarray of size “k” and then take the maximum out of those sum values.

Can you relate this problem with the previous one?

Take a Pause and Think !!!

The brute force approach is quite easy. We can simply calculate the sum of every contiguous subarray of size “k” and take the maximum out of all.

Java

Python

C++

import java.io.*;
class Innoskrit {
    public static int maxSumSubarraySumKSize(int arr[], int k) {
        int n = arr.length;
        int ans = Integer.MIN_VALUE;
        for(int i = 0; i < n - k + 1; i++) {
            int sum = 0;
            for(int j = i; j < i + k; j++) {
                sum += arr[j];
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
   
    public static void main (String[] args) {
        System.out.println(maxSumSubarraySumKSize(new int[] {2, 6, -9, 7, -1, 5, 4}, 3));
        System.out.println(maxSumSubarraySumKSize(new int[] {5, 2, -4, 9, -8, 3, -1, 5}, 5));
    }
}

import math
 
def maxSumSubarraySumKSize(arr, k):
     
    ans = -math.inf
    for i in range(len(arr) - k + 1):
        sum = 0
        for j in range(i, i + k):
            sum += arr[j]
        ans = max(ans, sum)
    return ans
              
if __name__ == '__main__':
    print(maxSumSubarraySumKSize([2, 6, -9, 7, -1, 5, 4], 3))
    print(maxSumSubarraySumKSize([5, 2, -4, 9, -8, 3, -1, 5], 5))

#include<bits/stdc++.h>
using namespace std;

class Innoskrit {
    public:
        static int maxSumSubarraySumKSize(const vector<int>& arr, int k) {
            int n = arr.size();
            int ans = INT_MIN;
            for(int i = 0; i < n - k + 1; i++) {
                int sum = 0;
                for(int j = i; j < i + k; j++) {
                    sum += arr[j];
                }
                ans = std::max(ans, sum);
            }
            return ans;
        }
};
  
int main(int argc, char * argv[]) {
    cout << Innoskrit::maxSumSubarraySumKSize(vector<int>{2, 6, -9, 7, -1, 5, 4}, 3) << endl;
    cout << Innoskrit::maxSumSubarraySumKSize(vector<int>{5, 2, -4, 9, -8, 3, -1, 5}, 5);
}

Time Complexity: O(n * k)

This is because for every element in the input array we are calculating the sum of every next k element and then taking max.

Efficient Approach with Sliding Window:

If you will see the above approach carefully you will find out that there is some part that we are repeating in every iteration.

Here is the visual representation of the algorithm.

So, we are treating each contiguous subarray as a sliding window of size k = 3.

This means when we will move to the next element we will simply slide the window by one element and we will subtract the element going out of the window and add the one which is now newly included in the window.

Our algorithm will look like this:

Code:

Java

Python

C++

import java.io.*;
class Innoskrit {
    public static int maxSumSubarraySumKSize(int arr[], int k) {
        int n = arr.length;
        int ans = Integer.MIN_VALUE;
        int windowSum = 0;
        int windowStart = 0;
        for (int windowEnd = 0; windowEnd < n; windowEnd++) {
            windowSum += arr[windowEnd];
            if(windowEnd >= k - 1) {
                ans = Math.max(ans, windowSum);
                windowSum -= arr[windowStart];
                windowStart++;
            }
       }
       return ans;
   }
   
    public static void main (String[] args) {
        System.out.println(maxSumSubarraySumKSize(new int[] {2, 6, -9, 7, -1, 5, 4}, 3));
        System.out.println(maxSumSubarraySumKSize(new int[] {5, 2, -4, 9, -8, 3, -1, 5}, 5));
    }
}

import math
 
def maxSumSubarraySumKSize(arr, k):
    ans = -math.inf
    windowSum = 0
    windowStart = 0
  
    for windowEnd in range(len(arr)):
        windowSum += arr[windowEnd]
        if windowEnd >= k - 1:
            ans = max(ans, windowSum)
            windowSum -= arr[windowStart]
            windowStart += 1
  
    return ans
  
if __name__ == '__main__':
    print(maxSumSubarraySumKSize([2, 6, -9, 7, -1, 5, 4], 3))
    print(maxSumSubarraySumKSize([5, 2, -4, 9, -8, 3, -1, 5], 5))

#include<bits/stdc++.h>
using namespace std;

class Innoskrit {
    public:
        static int maxSumSubarraySumKSize(const vector<int>& arr, int k) {
            int n = arr.size();
            int ans = INT_MIN;
            int windowSum = 0;
            int windowStart = 0;
            for(int windowEnd = 0; windowEnd < n; windowEnd++) {
                windowSum += arr[windowEnd];
                if(windowEnd >= k - 1) {
                    ans = std::max(ans, windowSum);
                    windowSum -= arr[windowStart];
                    windowStart++;
                }
            }
            return ans;
        }
};
  
int main(int argc, char * argv[]) {
    cout << Innoskrit::maxSumSubarraySumKSize(vector<int>{2, 6, -9, 7, -1, 5, 4}, 3) << endl;
    cout << Innoskrit::maxSumSubarraySumKSize(vector<int>{5, 2, -4, 9, -8, 3, -1, 5}, 5);
}