双指针
问题转化成求一段$[l,r]$满足里面的品种$ID$最多只能有$2$种,然后求$[l,r]$里面出现次数最多的那个$ID$的数目
我们可以枚举$r$,定义$l$表示所有满足$[l’,r]$中品种$ID$最多只有2种的$l’$中最小的那个
显然我们$r$往右移动时,$l$也是单调往右移动,所以可以用双指针
故我们答案就是所有$[l,r]$中出现次数最多的那个$ID$的数目,可以用$map$弄
Code:
时间复杂度:$O(nlogn)$
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[1100];
map<int,int>cnt;
int main()
{
int n;
cin>>n;
int res=0,ans=0;
for(int i=1,j=1;i<=n;i++){
scanf("%d",&a[i]);
cnt[a[i]]++;
if(cnt[a[i]]==1){
res++;
}
while(res>2){
cnt[a[j]]--;
if(!cnt[a[j]]){
res--;
cnt.erase(a[j]);
}
j++;
}
for(auto [x,y]:cnt)ans=max(ans,y);
}
cout<<ans<<endl;
return 0;
}