题目在这里:https://www.luogu.com.cn/problem/P1114
#include <bits/stdc++.h>
using namespace std;
int l[200010],r[200010],sum1,sum0,ans,n;
int main()
{
cin>>n;
for (int i=1;i<=n;i++){
int x; cin>>x;
sum1+=(x==1), sum0+=(x==0);
int t=sum0-sum1+n;
if (!l[t]&&t!=n) l[t]=i; else r[t]=i;
}
for (int i=0;i<=2*n;i++) ans=max(ans,r[i]-l[i]);
cout<<ans<<endl;
return 0;
}
sum0-sum1表示的是0与1数量的差值,可能为负数,加上n就转为非负数了。l[t]表示的是当人数最少的时候,0与1差值为t时,此时的人数i,当l[t]为0时,代表在之前的遍历中还没有出现0与1差值为t,所以将此时的人数i赋值给它。当t=n时表示此时0和1的数量相同,l[n]必须保持为0;r[t]表示0与1差值为t时,此时人数的最大值i,l[t]不等于0则表示之前出现过0与1差值为t,后续只更新r[t],当t==n时,此时的人数i符合0与1数量相同。
r[i]-l[i]表示0和1数量相同时的人数,当i为n时,此时0与1数量本就相同所以保持l[n]为0。