To find maximum of the numbers under Sliding Window
Question
Get the sliding window size k and print the maximum of the numbers under the sliding window.
Example :
Consider a sliding window of size k equals 3. Let the array be [3,2,7,8,5] the output should print 7 as the first output, then 8. Final output must be [7,8,8]
Logic
- If the size is 3 we find the largest among the 3 numbers under the sliding window and increment sliding window by one.
- When the sliding window moved one position, check whether the new item is large than the previous max.
- If greater we will not compare all the items on next iteration. Just compare new item and max.
- Because the other elements will be smaller than max.
Algorithm
- First, find the max of numbers under the sliding window and set the flag as 1.
- Increment the start and end positions of the window.
- If the flag is 1 check whether the new element is larger or equal to the max and set flag 1 if true.
- If the element is small then set the flag as 0.
Program
#include<iostream> using namespace std; int main() { int n,i,k,arr[10],st,en,j,flag=0,ma; cin>>n; for(i=0;i<n;i++) cin>>arr[i]; cout<<"enter window size : "; cin>>k; //each time increment start and end pt by 1 for(st=0,en=k-1;en<n;st++,en++) //loop till the window reach end(n) { if(flag == 0) { ma= arr[st]; for(j=st;j<=en;j++) // compare all items of window { if(arr[j]>ma) { ma= arr[j]; flag= 1; //need not check all the items next time } } cout<<ma<<" "; } else{ if(ma<arr[en]|| ma==arr[en]) //if max is lesser than new element of window { cout<<arr[en]<<" "; ma = arr[en]; flag=1; //so need not check all items of window next time } else { flag=0; //check all the items of window next time to find max cout<<ma<<" " ; } } } return 0; }