PS：声明，本做法由同机房巨佬

提供一个代码实现非常简单十分简短的做法。

返璞归真，状态没必要设置那么复杂，设 $f_i$ 表示考虑到第 $i$ 位的答案。显然的，对于每一个位置 $i$ 可以令 $f_i = f_{i-1}$。

用 $lst_i$ 记录 $i$ 上一次出现的位置，初始化令所有的 $lst_i = 0$，每遍历到一个位置，动态更新 $lst_{a_i} = i$。然后枚举区间更新 $f_i$，也可以预处理出来一个 $g$ 数组辅助转移，复杂度 $O(n^2)$。

50pts code

使用前缀和优化，每当 $a_i=a_{i-1}$ 时，更新前缀和数组 $s_i$。最后对于 $a_i$ 如果 $lst_{a_i}$ 存在，对于 $f_i$ 的转移为：

$$f_i=\max_{i=1}^{n}\{f_{lst_{a_i}+1}+a_i+s_i-s_{lst_{a_i}}\}$$

最终的答案为 $f_n$。

复杂度 $O(n)$。

#include <bits/stdc++.h>

#define int long long
#define rint register int
#define endl '\n'
#define m(a) memset(a, 0, sizeof a)

using namespace std;

const int N = 1e6 + 5;

int n, T;
int a[N], lst[N], f[N];
int s[N], ans; 

signed main() 
{
	cin >> T;
	while (T--) 
	{
		cin >> n;
		m(a), m(lst), m(f), m(s);
		for (rint i = 1; i <= n; i++) cin >> a[i];
		for (rint i = 2; i <= n; i++) s[i] = (a[i] == a[i - 1] ? s[i - 1] + a[i] : s[i - 1]);
		for (rint i = 1; i <= n; i++) 
		{
			f[i] = f[i - 1];
			if (lst[a[i]]) f[i] = max(f[i], f[lst[a[i]] + 1] + a[i] + s[i] - s[lst[a[i]] + 1]);
			lst[a[i]] = i;
		}
		cout << f[n] << endl;
	} 
	return 0;
}

GD-S01309李子优深圳中学(高一):

#include <bits/stdc++.h>
typedef long long LL;
typedef std::pair<int, int> pii;
#define fi first
#define se second
#define MP std::make_pair

int read()
{
    int s = 0, f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f ^= (c == '-');
    for (; isdigit(c); c = getchar()) s = s * 10 + (c ^ 48);
    return f ? s : -s;
}
template<typename T> T& Fmin(T& x, T y){ return x = x < y ? x : y; }
template<typename T> T& Fmax(T& x, T y){ return x = x < y ? y : x; }
const int MAXN = 200005, inf = 0x3f3f3f3f, V = 1000000, MAXV = 1000006;const LL INF = 0x3f3f3f3f3f3f3f3fll;
int n, a[MAXN];
LL f[MAXV], mx, dlt;
void mian()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    memset(f, ~0x3f, sizeof f), f[0] = mx = 0, dlt = 0;
    for (int i = 2; i <= n; i++)
    {
        LL val = std::max(dlt + mx, dlt + f[a[i]] + a[i]);
        if (a[i] == a[i - 1]) dlt += a[i];
        Fmax(mx, val - dlt), Fmax(f[a[i - 1]], val - dlt);    
    }
    printf("%lld\n", mx + dlt);
}
int main()
{
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    for (int T = read(); T--; ) mian();
    return 0;
}

GD-S02955陈可佳广州市铁一中学(高一):

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

template<typename T>
inline void read(T &x)
{
    x=0;
    T w=1;
    char c=getchar();
    while(c<'0'||c>'9') w=(c=='-'?-w:w),c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    x*=w;
}

typedef long long ll;

const int S=200005,MS=1000005;
const ll inf=1e17; 

int n,a[S];
ll sm[S];
ll f[S],g[MS];

inline void tmax(ll &x,ll y)
{
    x=max(x,y);
}

inline void slove()
{
    read(n);
    int mx=0;
    for(int i=1;i<=n;i++) read(a[i]),mx=max(mx,a[i]);
    for(int i=1;i<=n;i++)
    {
        sm[i]=sm[i-1];
        if(i>1&&a[i]==a[i-1]) sm[i]+=a[i];
    }
    for(int i=0;i<=n;i++) f[i]=-inf;
    for(int i=0;i<=mx;i++) g[i]=-inf;
    f[0]=0;
    f[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(a[i]==a[i-1]) tmax(f[i],f[i-1]+a[i]);
        else tmax(f[i],f[i-1]);
        tmax(f[i],sm[i-1]+g[a[i]]+a[i]);
        tmax(g[a[i-1]],f[i]-sm[i]);
    }
    ll ans=0;
    for(int i=1;i<=n;i++) tmax(ans,f[i]+sm[n]-sm[i]);
    printf("%lld\n",ans);
}

int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int T;
    read(T);
    while(T-->0) slove();
    return 0;
}

GD-S00550吴同春中山市中山纪念中学(高一):

#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=(l);i<=(r);++i)
#define fd(i,l,r) for(int i=(l);i>=(r);--i)
#define fu(i,l,r) for(int i=(l);i<(r);++i) 
#define ll long long
using namespace std;
const int N=200007,M=1e6+7;
const ll inf=1e18;
int n,a[N];
ll s[N],f[N],ans,p[M],mx;
void ins(int x,ll y)
{
    p[x]=max(p[x],y);
    mx=max(mx,y);
}
ll qry(int x)
{
    return max(p[x]+x,mx);
}
void work()
{
    scanf("%d",&n);
    int maxa=0;
    fo(i,1,n) scanf("%d",&a[i]),maxa=max(maxa,a[i]);
    fo(i,2,n) s[i]=(a[i]==a[i-1]?a[i]:0)+s[i-1];
    fo(i,0,maxa) p[i]=-inf;ans=s[n];mx=-inf;
    fo(i,1,n)
    {
        f[i]=max(qry(a[i])+s[i-1],s[i-1]);
        ins(a[i-1],f[i]-s[i]);
        ans=max(ans,s[n]-s[i]+f[i]);
    }
    printf("%lld\n",ans);
}
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--) work();
    return 0;
}