题解

思路推导

先固定三段回文两侧使用的数值 $x$，再固定两侧各取多少个 $x$。为了给中间段留下尽可能大的选择范围，左侧应取最靠左的若干个 $x$，右侧应取最靠右的同样多个 $x$。此时中间段只能位于这两个边界之间，并且应全部选择该区间内出现次数最多的某个数值。

因此，只要枚举数值 $x$ 和两侧各取的个数 $k$，答案候选就是 $2k$ 加上对应开区间内某个数值的最大出现次数。完全不取两侧时，答案等于整个序列中出现次数最多的数值的频次。

做法

记录每种数值的全部出现位置。对每个可能的 $x$ 单独处理：从最外侧的一对 $x$ 开始，维护当前两个边界之间各数值的出现次数。随后每次把左右边界各向内推进到下一对 $x$，并删除离开中间区间的元素。用出现次数的计数表维护当前最大的中间频次。

一个固定的 $x$ 在整个推进过程中，每个位置至多被加入或删除常数次，所以处理一个 $x$ 的代价是线性的。值域只有 $200$，依次处理所有可能的 $x$ 即可。

正确性证明

考虑任意一个最优三段回文，其两侧数值为 $x$，两侧各有 $k$ 个元素。把左侧所选的 $k$ 个 $x$ 替换为序列中最靠左的 $k$ 个 $x$，并把右侧替换为最靠右的 $k$ 个 $x$，不会破坏子序列顺序，而且只会扩大可供中间段选择的区间。

在边界固定后，中间段必须只含一种数值。选择该开区间内出现次数最多的数值，显然能够得到这一对边界下最长的中间段。因此算法枚举到最优解对应的 $x$ 和 $k$ 时，一定会得到不小于最优解的候选值；另一方面，每个候选都由合法的左右两段和合法的单值中间段组成，不会超过最优值。故算法得到的答案恰为最优答案。

复杂度分析

设数值上界为 $V=200$。每组测试数据的时间复杂度为 $O(Vn)$，空间复杂度为 $O(n+V)$。