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:
- Input the array size, window size and the array elements.
- If the array size is greater than the window size, then call the function to find the maximum sum.
- 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.
- 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 >> 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(k*n)
# Optimized Algorithm(Sliding Window)
- Input the array size, window size and the array elements.
- If the array size is greater than the window size, then call the function to find the maximum sum.
- Find the sum of first k consecutive elements of the array and then store in a variable which is the window sum.
- 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.
- Compare the sum and store the maximum sum value in a separate variable.
- 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.