提交记录
显然我的代码是 $O(n^2)$，本意是想先写个暴力看看对不对，然后再优化，结果直接过了

#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define M 1000005
#define int long long
int T, n;
int a[N];
int vis[M], pre[N], dp[N];
void solve()
{
	memset(vis, 0, sizeof(vis));
	memset(vis, 0, sizeof(pre));
	memset(vis, 0, sizeof(dp));
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lld", a + i);
	for (int i = 1; i <= n; i++)
	{
		if (vis[a[i]])
			pre[i] = vis[a[i]];
		else
			pre[i] = i;
		vis[a[i]] = i;
	}
	for (int i = 1; i <= n; i++)
	{
		int sum = 0;
		dp[i] = dp[i - 1];
		if (pre[i] == i - 1)
		{
			dp[i] += a[i];
			continue;
		}
		if (pre[i] != i)
		{
			for (int j = pre[i] + 2; j < i; j++)
				if (a[j] == a[j - 1])
					sum += a[j];
			dp[i] = max(dp[i], dp[pre[i] + 1] + sum + a[i]);
		}
	}
	for (int i = 1; i <= n; i++)
		printf("%lld ", dp[i]);
	puts("");
	printf("%lld\n", dp[n]);
}
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("data.in", "r", stdin);
	// freopen("data.out", "w", stdout);
#endif
	scanf("%lld", &T);
	while (T--)
		solve();
	return 0;
}