DP+离谱优化

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int MAXN=2e5+7;
long long n,T,a[MAXN],s[MAXN],f[MAXN],l[MAXN],ans,t[1000005];
int main()
{
	//freopen("color.in","r",stdin);
	//freopen("color.out","w",stdout);
	scanf("%lld",&T);
	while(T--)
	{
		memset(f,0,sizeof f);
		memset(t,0,sizeof t);
		scanf("%lld",&n);
		for(int i=1;i<=n;i++)scanf("%lld",a+i),l[i]=t[a[i]],t[a[i]]=i;
		for(int i=2;i<=n;i++)f[i]=s[i]=s[i-1]+(a[i]==a[i-1]?a[i]:0);
		for(int i=2;i<=n;i++)
		{
			//Form1
			f[i]=max(f[i],f[i-1]+(a[i]==a[i-1]?a[i]:0));
			for(int j=l[i],times=0;j;j=l[j])
			{
				if(f[i]<=f[j+1]+s[i-1]-s[j+1]+a[i])times=0,f[i]=f[j+1]+s[i-1]-s[j+1]+a[i];
				else if((++times)>=100)break;
			}
		}
		ans=0;
		for(int i=1;i<=n;i++)ans=max(ans,f[i]);
		printf("%lld\n",ans);
	}
	return 0;
}