Max element in current element. Implementation using the concept of doubly ended queued but with simple arrays and two pointers.

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <queue>

using namespace std;

/*Let the Current window size be K.
10 Elements and 4 is size of the window
Input : 10 3
1 5 2 6 4 8 6 2 3 5

Output: 5 6 6 8 8 8 6 5
*/

int a[1000];
int q[1000];
vector<int> ans;
int main()
{ //Front of queue is the side where we enter new element.
//back is the side from which we remove old element.
//Here basically a doubly ended queue is implemented using
//simple array and two pointers pointing to the back and
//front respectively. :-)
int n, k;
int front1 = -1, back1 = 0;
cin >> n >> k;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++){

while(front1 >= back1 && q[front1] < a[i]) //While atleast 1 element is present and
//current element is greater then front
//of queue, remove from front.
front1--;
q[++front1] = a[i]; //Add new element to front.

if(i >= k && q[back1] == a[i-k]) //If current element is equal to element
//at the back, remove front the back.
back1++;
if(i >= k -1) //Print after iterating k-1 times
cout << q[back1] << endl;
// for(int j = back1; j <= front1; j++) //Can be used to print current status of queue
// cout << q[j] << " " ;
// cout << endl;
}

}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s