因为题解区没法发了，所以在讨论区和大家讨论一下对 PassName & hanss6 的这个题解 的看法，不是讨论区题解（

如果我的理解有误，真诚希望原作者 / 各位大佬批评指正

我认为这个做法（尤其是代码）相当巧妙，但是我在思考这个做法的过程中发现这个算法并非看上去那么容易，而且讨论区有诸多关于正确性的顾虑。实际上这个代码利用了很多 trick，作者对做法的叙述本身带有很强的迷惑性，比如 $a_i = a_{i-1}$ 时实际上 $lst_{a_i} = i-1$，那么计算 $f_i$ 的时候就会调用 $f_i$ 本身

那这个会不会产生问题呢？并不会，因为已经赋值了 $f_i = f_{i-1}$，这里实际上计算的是 $\color{green}f_{i-1} + a_i$。所以如果你“等价的”写作 $f_i = \max(f_{i-1}, f_{lst_{a_i} + 1} + \cdots)$ 就会 WA。

接下来是形式化的解释。

首先明确 $f_i$ 的定义是 当前考虑 $[1, i]$，与 $a_i$ 完全相同的末尾若干个数强制视作一段的开头，这种情况下的 $[1, i]$ 的最佳收益。 比如 $a_i = 7$，那 $f_i$ 描述的分段就是形如

$a_1, a_2, \color{red}\cdots, a_{i-k}, \color{blue}7, 7, \cdots, a_i=7$

我们解释程序的行为为什么符合这个描述。首先 $a_i = a_{i-1}$ 时，最优方案肯定是 $i$ 继承 $i-1$ 的颜色，所以程序的行为按照上面引言所述，就是 $\color{green}f_i = f_{i-1} + a_i$。

于是程序会把相同的一段数缩点，接下来不妨设相邻的两个数都是不同的。 $f_i$ 代表 $i$ 恰好是新一段的开头，$i-1$ 是上一段的结尾。

$a_1, a_2, \color{red} \cdots, a_{i-1}, \color{blue} a_i$

接下来就是评论区讨论最多的问题：为什么一定从 $lst_{a_i} + 1$ 处转移？（这里已经有 $lst_{a_i} \ne i-1$）

我们需要分别从最优方案 $a_i$ 产生贡献 / 不产生贡献两个角度来说明。

情况 1：如果 $a_i$ 产生贡献

那么与 $a_i$ 匹配的一定是 $lst_{a_i}$ 处的值 $(*)$。画个图就是

$a_1, a_2, \color{blue}\cdots, a_{lst},\color{red} a_{lst + 1}, \cdots, a_{i-1}, \color{blue} a_i$

所以转移需要用到的是 $f_{lst \color{green}\bf+ 1}$，因为 $f$ 的下标是红色段的开头第一个数。

如若 $(*)$ 不然，那就是搬出了古早相同值 $a_{old} = a_i$ 进行匹配，我们作调整

只改变 $a_{lst}$ 的颜色，我们实现了收益增大。

情况 2：如果 $a_i$ 不产生贡献

那么 $f_{i-1}$ 就是我们需要的答案。这并不是特别 trivial，因为按照 $f_{i-1}$ 的定义我们需要 $i-1$ 独立成段。

$a_1, a_2, \color{blue}\cdots, a_{i-2},\color{red} a_{i-1}, \color{blue}a_i$

最优方案为什么一定是这样？我们再用调整法，假设上一个红色段很长

这样答案不会下降，因为根据“不妨设”，有 $a_{i-2} \ne a_{i-1}$，所以 $a_{i-1}$ 原先必没有贡献，而原先 $a_i$ 也没贡献，现在一调整，两者只会更好。所以 $i-1$ 一定能独立成段。

最后一个我认为需要解答的点，是为什么这个顶一下，输出的答案是 $f_n$？实际上这个类比“情况 2”不难看出，$a_n$ 独立成段，一定是最优的。