难度： 黄

算法： 动态规划，哈希

考虑到 $n\le 10^6$，可用 $O(nlogn)$ 算法。

首先，对于 $i$，处理出小于 $i$ 的最大的能使 $a_i=a_j$ （$a$ 为输入数据）的 $j$，记为 $s_i$。

动态规划。记 $f_i$ 为以第 $i$ 项结尾的答案，则有 $f_i=min(f_{i-1}+1,i-s_i)$，很好推。最终答案为 $max(f_i)$。

排序部分 $O(nlogn)$，其余部分 $O(n)$，可以草过去。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,s[1000100],f[1000100],ans;
//s[i]记录上一个与第i项相同的数，f[]为动态规划数组 
struct nd{
	int v,d;
}a[1000100];//原始数组，v数值，d编号 
bool cmp(nd p,nd q){
	if(p.v!=q.v) return p.v<q.v;
	return p.d<q.d;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].v),a[i].d=i;//输入 
	sort(a+1,a+n+1,cmp);//排序 
	for(int i=2;i<=n;i++){//求s数组 
		if(a[i].v==a[i-1].v){
			s[a[i].d]=a[i-1].d;
		}
	}
	for(int i=1;i<=n;i++){//dp
		f[i]=min(f[i-1]+1,i-s[i]);
		ans=max(ans,f[i]);
	}
	printf("%d",ans);//输出 
	return 0;
}