[传送门]
其实就是这些数字前面能加正负号，在满足正负号均出现的情况下价值最大。
那么就可以无脑DP
$f[i][j][k]$表示到了第$i$位，正号是否出现($j$、$k$为$0$或$1$)能得到的最大价值
答案就是$f[n][1][1]$
$n$为1的时候特判一下就行
举几个例子就能发现加正负号这个方法是对的。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 5e5 + 7; ll a[N], dp[N][2][2]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); dp[1][1][0] = a[1]; dp[1][0][1] = -a[1]; dp[1][1][1] = -1e18; for (int i = 2; i <= n; i++) { dp[i][1][0] = dp[i - 1][1][0] + a[i]; dp[i][0][1] = dp[i - 1][0][1] - a[i]; dp[i][1][1] = max(dp[i - 1][1][0] - a[i], max(dp[i - 1][0][1] + a[i], max(dp[i - 1][1][1] + a[i], dp[i - 1][1][1] - a[i]))); } if (n == 1) printf("%lld\n", a[1]); else printf("%lld\n", dp[n][1][1]); return 0; }
原文：https://www.cnblogs.com/Mrzdtz220/p/11673010.html
