AcWing 5481. 双端队列
原题链接
中等
作者:
小周不会做题
,
2024-04-04 20:46:48
,
所有人可见
,
阅读 2
#include<iostream>
using namespace std;
const int N=2e5+10;
int a[N];
int judge(int l,int r,int cnt)
{
int res=0;
while(l<=r)
{
if(a[l]<a[r]&&a[l]>cnt||a[r]<=cnt&&a[l]>cnt)
{
res++;
cnt=a[l];
l++;
}
else if(a[r]<a[l]&&a[r]>cnt||a[l]<=cnt&&a[r]>cnt)
{
res++;
cnt=a[r];
r--;
}
else if(a[l]<=cnt&&a[r]<=cnt) return res;
else if(a[l]==a[r]&&a[l]>cnt)
{
res+=max(judge(l+1,r,a[l]),judge(l,r-1,a[r]));
//cout<<judge(l+1,r,a[l])<<" "<<judge(l,r-1,a[r]);
res++;
return res;
}
}
return res;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
//for(int i=1;i<=n;i++) cout<<a[i]<<" ";
if(a[1]<a[n]) cout<<judge(2,n,a[1])+1;
else if(a[1]>a[n]) cout<<judge(1,n-1,a[n])+1;
else cout<<max(judge(2,n,a[1]),judge(1,n-1,a[n]))+1;
return 0;
}