Maximum of all subarrays of size k (Sliding Window Technique)

Problem: The problem statement is quite simple to understand. The input contains an unsorted array with multiple elements in it. The output is the maximum current sum of the k consecutive elements.

Input: {1,9,5,6,4,7}, k=2

Output: 14

 

There are two approaches to solve it:

• Brute Force Approach: Use nested loops to calculate the current sum of the consecutive elements.
• Optimized Approach: Use a single loop to reduce the time complexity for the same.

# Brute Force Algorithm:

1. Input the array size, window size and the array elements.
2. If the array size is greater than the window size, then call the function to find the maximum sum.
3. Use the first loop to iterate the k-sized loop to find the window sum and after each complete iteration of the second loop (window sized loop) check for the max sum. 
4. Finally, print the maximum sum value with its window size.

Code:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
void ms(int a[], int n, int k){
int i, j, cur, maxsum = INT_MIN;
for (i = 0; i <= n - k; i++){
cur = 0;
for (j = 0; j < k; j++){
  cur = cur + a[i + j];

}

maxsum = max(cur, maxsum);

}
cout << "Maximum sum of " << k << " consecutive elements is: " << maxsum;
}
int main(){
int len, k, i;
cout << "Enter the number of elements : " << endl;
cin >> len;
cout << "Enter the window size : " << endl;
cin >> k;
int array[len];
cout << "Enter the array elements : " << endl;
for (i = 0; i < len; i++){
cin &gt;&gt; array[i];

}
cout << "Original array is: " << endl;
for (i = 0; i < len; i++){
cout &lt;&lt; array[i] &lt;&lt; " ";

}
cout << endl;
if (len < k){
cout &lt;&lt; "Window size is larger than array size" &lt;&lt; endl;

} else {
ms(array, len, k);

}
return 0;
}

Output:

Enter the number of elements:
8
Enter the window size:
2
Enter the array elements:
1
-3
9
-5
-2
6
4
-7
Original array is:
1 -3 9 -5 -2 6 4 -7
Maximum sum of 2 consecutive elements is: 14

Time Complexity: O(k*n)

# Optimized Algorithm(Sliding Window)

1. Input the array size, window size and the array elements.
2. If the array size is greater than the window size, then call the function to find the maximum sum.
3. Find the sum of first k consecutive elements of the array and then store in a variable which is the window sum. 
4. Now iterate through rest of the elements from k till the last element in the array by adding one element and eliminating the first element. 
5. Compare the sum and store the maximum sum value in a separate variable.
6. After completing the iteration, print the maximum sum value with its window size.

Code:

#include<bits/stdc++.h>
using namespace std;
void ms(int a[], int n, int k){
int i, j, maxsum = 0;
for (i = 0; i < k; i++){
maxsum = maxsum + a[i];
}
int wsum = maxsum;
for (i = k; i < n; i++){
wsum = wsum + a[i] - a[i - k];
maxsum = max(maxsum, wsum);
}
cout << "Maximum sum of " << k << " consecutive elements is: " << maxsum;
}
int main(){
int len, k, i;
cout << "Enter the number of elements : " << endl;
cin >> len;
cout << "Enter the window size : " << endl;
cin >> k;
int array[len];
cout << "Enter the array elements : " << endl;
for (i = 0; i < len; i++){
cin >> array[i];
}
cout << "Original array is: " << endl;
for (i = 0; i < len; i++){
cout << array[i] << " ";
}
cout << endl;
if (len < k){
cout << "Window size is larger than array size" << endl;
} else {
ms(array, len, k);
}
return 0;
}

Output:

Enter the number of elements:
8
Enter the window size:
2
Enter the array elements:
1
-3
9
-5
-2
6
4
-7
Original array is:
1 -3 9 -5 -2 6 4 -7
Maximum sum of 2 consecutive elements is: 14

Time Complexity: O(n)

This way with more practises of data structures and algorithms we can approach towards efficient source codes of any particular programs.