「2.1」收集雪花
题目描述
不同的雪花往往有不同的形状。在北方的同学想将雪花收集起来，作为礼物送给在南方的同学们。一共有 n 个时刻，给出每个时刻下落雪花的形状，用不同的整数表示不同的形状。在收集的过程中，同学们不希望有重复的雪花。你可以从任意 a 时刻开始，在 b 时刻停止。a 到 b 时刻中间的雪花也都将被收集。他们希望收集的雪花最多。
输入格式
第一行一个正整数 n；
第 2 行 n 个非负整数表示 n 个时刻雪花的形状。
输出格式
最多能收集雪花的数量。
样例输入1
5
1 2 3 2 1
样例输出1
3
注释说明
注：使用读优化！！！
对于 97 分的数据，1≤n≤10^6,0≤xi≤10^8。（为原始数据）
应用户要求，加入 3 分的数据，1≤n≤10^6,0≤xi≤10^9。
#include<bits/stdc++.h>
using namespace std;
int n,a[1000003],last[1000005],ans=1,b[1000005];
map<int,int>mp;
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
int tot=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=tot;i++){
mp[b[i]]=i;
}
for(int i=1,j=1;i<=n;i++){
int laai=last[mp[a[i]]];
// printf("%d\n",laai);
if(laai>=j){
j=laai+1;
}
last[mp[a[i]]]=i;
ans=max(ans,i-j+1);
}
printf("%d\n",ans);
}
/*
8
2 8 2 4 5 1 2 4
*/