题解 | #超现实子序列#

首先考虑暴力dfs：每次确定一个起点后不断搜索最近的下一个值的位置。提交后发现T了，然后想到如果一个起点的长度很大，并且这个值在前面出现了好多次，那么复杂的很大，几乎是n^2，所以考虑如果有多个相同的数，一定是选最前面那个作为起点最优，所以用map记录一下每个值作为起点的最长长度，类似记忆搜。

int n;
int a[maxn];
int ans=1;
vector <int> G[maxn];
map <int,int> mp;

void dfs(int s1,int pos,int len){
	ans=max(ans,len);
    mp[s1]=len;
	len++;
	int need=s1;
	if(len&1) need-=len/2;
	else need+=len/2;
	
	if(need>=1 && need<=1000000 && G[need].size()){
		int p=upper_bound(G[need].begin(),G[need].end(),pos)-G[need].begin();
		if(G[need][p]>pos){
			dfs(s1,G[need][p],len);
		}
	}
}

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		G[a[i]].pb(i);
	}
	
	for(int i=1;i<=n;i++){
        if(mp[a[i]]) continue;
		dfs(a[i],i,1);
	}
	cout<<ans<<endl;
}