题解与来源题共享。已有题解默认通过；新增或编辑后需由来源域管理员审核。待审核、驳回题解仅作者和审核管理员可见。来源域：system

• 0

  DoubleQLzn LV 5 @ 2026-8-31 21:11:51

  令 $F_{i,j}$ 为考虑 $[1,i]$，最后一个与 $i$ 异色的元素值为 $j$ 的可能性；

  • 与 $a_{i-1}$ 同色，$F_{i,j}=F_{i-1,j}+[A_i=A_{i-1}]\cdot A_i$。
  • 与 $a_{i-1}$ 异色，$F_{i,a_{i-1}}=\max(F_{i-1,a_i}+a_i,F_{i-1,j})$

  使用数据结构维护，把全局加的东西拉出来，可以使用前后缀最大值和单点 upd 的 BIT 维护 dp 的过程。做完了。

  时间复杂度 $O(n\log V+V\log V)$。