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
Example 2:
Input:
arr : [5, 2, -4, 9, -8, 3, -1, 5] k : 5
Output:
8
If you have jumped directly to this problem and you have not understood what exactly Sliding Window Pattern is. Then we would suggest you go and read Sliding Window Pattern.
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.
Let’s look at the code for the brute force approach.
Java Code:
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));
}
}
CPP Code:
#include <iostream>;
#include <vector>
#include <climits>
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);
}
Python Code:
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))
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.
In the first iteration, we took the sum of (2, 6, -9) and in the second iteration sum of (6, -9, 7). But if we see, we already have the sum of 6 and -9 from our previous iteration and we are repeating this unnecessarily in the next iteration. Now, our task is to identify how we can utilize this sum.
Let’s visualize it:
So, we are treating each contiguous subarray as a sliding window of size 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.
Let’s look at the code for the above scenarios:
Java Code:
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));
}
}
CPP Code:
#include <iostream>
#include <vector>
#include <climits>
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);
}
Python Code:
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))
In this efficient approach, we are traversing every element only once. Hence, Time Complexity will be O(n).
Since we are not using any extra space except for some variables. Therefore, Space Complexity will be O(1).
Understood Right?
Now, check out more interesting problems on Sliding Window Pattern.