设 $f(i,j)$ 为 $1$ ~ $i$ 格（$j$ ~ $i$ 同色）所得最大得分

$$f(i,i)=\max_{j=0}^{i-1} f(i-1,j+1)+A_i[A_j=A_i]$$

$$f(i,j)=f(i-1,j)+A_i[A_i=A_{i-1}]\ \ (j<i)$$

---

$$\text{let } E_i=A_i[A_i=A_{i-1}],\ S_i=\sum_{j=1}^i E_i$$

$$f(i,j)=f(j,j)+\sum_{k=j+1}^{i}E_i=f^*(j)+S_i-S_j$$

---

$$\begin{align*} f^*(i)=f(i,i)&=\max_{j=0}^{i-1} f(i-1,j+1)+A_i[A_j=A_i] \\ &=\max_{j=0}^{i-1}f^*(j+1)+S_{i-1}-S_{j+1}+A_i[A_j=A_i] \\ &=S_{i-1}+\max_{j=0}^{i-1}\left(g(j+1)+A_i[A_j=A_i]\right) \\ &=S_{i-1}+\max\left\{\max_{j=1}^{i}g(j),\ A_i+\max_{j=0}^{i-1}[A_j=A_i]g(j+1)\right\} \end{align*}$$

---

$$\begin{align*} F(i)&=\max_{j=1}^{i}f(i,j) \\ &=\max_{j=1}^{i}f^*(j)+S_i-S_j \\ &=S_i+\max_{j=1}^{i}f^*(j)-S_j \\ &=S_i+\max_{j=1}^{i}g(j) \end{align*}$$

---

需要维护：

• $\max_{j=1}^{i}g(j)$

• $\max_{j=0}^{i-1}[A_j=A_i]g(j+1)$

后者离散化后开数组存即可。