思路与算法

利用红蓝对称性，固定最近位置所用颜色为当前色，prev为其末值。状态f[v]表示另一色末值v时的最优分数。新值x继续当前色时，所有状态统一增加G=(prev==x?x:0)；改用另一色时，最优来自max(max_v f[v],f[x]+x)，且另一色末值变成prev。用统一偏移offset和归一化数组d[v]=f[v]-offset维护，单点更新d[prev]并维护全局最大值即可。

正确性说明

任何合法染色的下一步只有沿用最近颜色或换色两类。前者得分仅依赖prev与x，所以统一增加G准确；后者只有另一色末值恰为x才得x，其余得0，故上述两项最大值穷尽所有旧状态。换色后重命名两色，新另一色末值是prev，保证状态语义不变。归一化只是同时减去同一偏移，不改变大小关系与转移，因此滚动计算得到最大分数。

复杂度

每组含值域数组初始化为O(V+n)时间、O(V)空间，V=10^6；总O(TV+∑n)，不能忽略每组清零。

易错点

同色的最近项才计分，不是前面任意同值。未使用另一色用专门初态；新候选必须在统一加G之前求得再减G归一化。总分需64位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    const long long NEG = -4000000000000000000LL;
    while (T--) {
        int n;
        cin >> n;
        vector<long long> d(1000001, NEG);
        d[0] = 0;
        long long best = 0, offset = 0;
        int last = 0;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            long long gain = x == last ? x : 0, candidate = max(best, d[x] + x) - gain;
            d[last] = max(d[last], candidate);
            best = max(best, d[last]);
            offset += gain;
            last = x;
        }
        cout << best + offset << "\n";
    }
}