To find maximum of the numbers under Sliding Window

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

  1. First, find the max of numbers under the sliding window and set the flag as 1.
  2. Increment the start and end positions of the window.
  3. If the flag is 1 check whether the new element is larger or equal to the max and set flag 1 if true.
  4. 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;
 }

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
5 1 vote
Article Rating
Subscribe
Notify of
guest
5.4K Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
5.4K
0
Would love your thoughts, please comment.x
()
x