Я борюсь с вопросом о хакерранке deque-stl . Я реализовал алгоритм, который находит максимальный элемент в окнах и сохраняет его индекс, а затем использует этот индекс максимального элемента в предыдущем окне, чтобы найти максимальный элемент в следующем окне, только если индекс максимального элемента лежит между индексами следующего окна. Используя этот алгоритм и предложения, упомянутые в комментариях, я реализовал этот обновленный алгоритм, но я все еще получаю ошибку неправильного ответа.
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int m,idx;
void maxinwindow(int arr[], int start, int end)
{
/*If the index of the maximum element in the previous window
is between the indexes of next windows then no need to compare
elements that were in previous window */
if(idx>=start)
{
if(arr[idx]>=arr[end])
{
m=arr[idx];
}
else
{
m=arr[end];
idx=end;
}
}
else
{
if(arr[start]>=arr[start+1])
m=arr[start];
else
m=arr[start+1];
for(int k=start+2;k<=end;k++)
{
if(arr[k]>=m)
{
m=arr[k];
idx=k;
}
}
}
}
int main()
{
int arr[100000];
int q;
cin>>q;
for(int i=1,size,ws;i<=q;i++)
{
m=0;
cin>>size; //Array size
cin>>ws; //Window Size
//Entering The Elements In The Array
for(int j=1;j<=size;j++)
{
cin>>arr[j];
}
//Boundary Condition i.e. Windows size is equal to 1
if(ws==1)
{
for(int j=1;j<=size;j++)
{
cout<<arr[j]<<" ";
}
}
else
{
for(int k=1;k<=ws;k++)
{
if(arr[k]>=m)
{
m=arr[k];
idx=k;
}
}
cout<<m<<" ";
for(int k=2,j;k<=(size-(ws-1));k++)
{
j=(k+(ws-1));
maxinwindow(arr,k,j);
cout<<m<<" ";
}
cout<<endl;
}
}
}