个人觉得挺妙的一个结论题。
首先不难发现每个数对答案的贡献是 (a_i) 或者 (-a_i)。
那么系数的序列应该有两个性质：必须存在两个相同的系数相邻。设有 (p) 个减号，(q) 个加号，满足 (2p+q equiv 1 pmod{3})。
证明后面再写。
那么知道这个性质，考虑记 (dp_{i,j,0/1,0/1}) 表示第 (i) 位，模 (3) 的余数，这一位的系数，是否存在两个相同的系数相邻的最大值。
时间复杂度 (O(n))。
注意要考虑到 +-+-+-... 或者 -+-+-+... 这类情况是不合法的。
结论的证明：
对于 (n in [1,3]) 结论显然正确。
对于 (n geq 4)，考虑合并之后 (p'=q+1,q'=p)。
那么就有 (2(2p'+q')=3q+5)。
显然 (3q+5 equiv 2 pmod{3})，所以 (2p+q equiv 1 pmod{3})。
#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define rep(i,a,n) for(reg int (i)=(a);(i)<=(n);++(i))
#define per(i,a,n) for(reg int (i)=(a);(i)>=(n);(i)--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define debug(typ...) fprintf(stderr, typ)
using namespace std;
const int iINF=numeric_limits<int>::max();
const ll lINF=numeric_limits<ll>::max();
int fastin() {
reg int x = 0, ch = getchar(), f = 0;
while(!isdigit(ch)) (ch == '-') && (f = 1), ch = getchar();
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
const int MAXN=2e5+10;
int n;
ll a[MAXN],dp[MAXN][3][2][2];
template<class typ>
void checkmax(reg typ &x,reg typ y) {
if(x<y) x=y;
}
void work() {
n=fastin();
rep(i,1,n) a[i]=fastin();
if(n==1) {
printf("%lld
",a[1]);
return;
}
memset(dp,-127,sizeof(dp));
dp[1][2][0][0]=-a[1],dp[1][1][1][0]=a[1];
rep(i,1,n-1) {
rep(j,0,2) {
checkmax(dp[i+1][(j+1)%3][1][1],max(dp[i][j][1][0],max(dp[i][j][1][1],dp[i][j][0][1]))+a[i+1]);
checkmax(dp[i+1][(j+1)%3][1][0],dp[i][j][0][0]+a[i+1]);
checkmax(dp[i+1][(j+2)%3][0][1],max(dp[i][j][0][0],max(dp[i][j][0][1],dp[i][j][1][1]))-a[i+1]);
checkmax(dp[i+1][(j+2)%3][0][0],dp[i][j][1][0]-a[i+1]);
}
}
printf("%lld
",max(dp[n][1][0][1],dp[n][1][1][1]));
}
signed main() {
int _=1;
// _=fastin();
while(_--) work();
return 0;
}