本题作为一道本人思考了50分钟没想出来的大思维题，我觉得可以用来扩宽一下大家的视野。
本题中，我们每次都会选取两个相邻的数 \(a_i\) 和 \(a_{i+1}\)，同时将这两位变为一位，这一位上填的数为 \(-(a_i+a_{i+1})\)。
很容易想到的一个 \(O(n^3)\) 的 dp 做法是区间 dp，设 \(f[l,r]\) 为区间 \([l, r]\) 的最大值，\(g[l,r]\) 为区间 \([l, r]\) 的最小值，我们就可以得到如下方程：
\[f[l, r] = f[l,r]=\max \limits _{k=l}^{r-1}\{ -(g[l, k]+g[k+1,r]) \} \]\[g[l, r] = g[l,r]=\min \limits _{k=l}^{r-1}\{ -(f[l, k]+f[k+1,r]) \} \]但是题目数据范围太大，无法承受。
我们可以考虑一下答案有没有什么性质。
一个比较显然的性质是：答案一定是 \(a\) 序列所有数加加减减得到的，更严谨地说，\(a\) 序列中每个数对答案的贡献取决于它在答案中的正负号。
因此我们可以考虑什么样的正负号排列才是合法的。
我们可以枚举一下 \(n = 1, 2, 3\) 的情况。
\(n = 1\)
符合要求的序列有 +。
\(n=2\)
符合要求的序列有 --。
\(n=3\)
符合要求的序列有 ++-, -++
能不能发现什么性质
我们统计一下 - 的数量 \(p\), + 的数量 \(q\)，我们可以很难发现一个规律：\(2p+q \equiv 1 \pmod{3}\)
证明：显然对于 \(n=1,2,3\) 的情况都成立，考虑当长度为 \(n\) 时的情况：
每个情况一定都是两种合法情况的组合，那么：
\[\begin{aligned} -[(2p_1+q_1)+(2p_2+q_2)] &\equiv -(1+1) \pmod{3} \\ &\equiv 1 \pmod{3} \end{aligned} \]证毕
但是还有一种情况：+-+-+-+-......。这种情况是不合法的。所以我们接下来还要考虑上这点。
想到这个性质之后我们就可以开始 dp 了，我们设 \(f[i][j][k][u]\) 表示当前考虑到第 \(i\) 个数，\(2p+q\) 在模 \(3\) 意义下为 \(j\)，上一个符号为 \(k\)，是否出现了两个相同符号相邻 \(u\)。
状态设计出来后就可以开始 dp 了。
\[f[i+1][(j+2)\bmod 3][0][u|(k==0)]\leftarrow f[i][j][k][u]-a_{i+1} \]\[f[i+1][(j+1)\bmod 3][1][u|(k==1)]\leftarrow f[i][j][k][u]+a_{i+1} \]然后就可以愉快 AC 力！
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll f[N][4][2][2];
ll a[N];
int n;
int main()
{
n = read();
for(int i = 1; i <= n; i ++ ) a[i] = read();
if(n == 1)
{
cout << a[1] << endl;
return 0;
}
memset(f, -0x3f, sizeof f);
f[1][1][1][0] = a[1], f[1][2][0][0] = -a[1];
for(int i = 1; i < n; i ++ )
for(int j = 0; j < 3; j ++ )
for(int k = 0; k < 2; k ++ )
for(int u = 0; u < 2; u ++ )
{
f[i + 1][(j + 2) % 3][0][u | (k == 0)] = max(f[i + 1][(j + 2) % 3][0][u | (k == 0)],
f[i][j][k][u] - a[i + 1]);
f[i + 1][(j + 1) % 3][1][u | (k == 1)] = max(f[i + 1][(j + 1) % 3][1][u | (k == 1)],
f[i][j][k][u] + a[i + 1]);
}
cout << max(f[n][1][0][1], f[n][1][1][1]) << endl;
return 0;
}