Codeforces 33C Wonderful Randomized Sum

题意

将序列的前面连续0个或多个数变成相反数，或者将后面连续0个或多个数变成相反数之后求整个序列和的最大值。

算法一

可以枚举1～i每个位置都取相反数之后，序列总和如何取最大，从前到后枚举一遍，从后往前再枚举一遍，然后取最大值。不过枚举效率太低，我们可以考虑先记录下每次枚举的最值
于是可以用：

• dp1[i]保存1～i位取反之后，前i个数能取得的最大和
• dp2[i]保存i～n位取反之后，后i个数能取得的最大和
• 最后答案是 m a x { d p [ i ] + d p [ i + 1 ] } , 0 ≤ i ≤ n + 1 max\{dp[i] + dp[i+1]\}, 0 \le i \le n+1 max{ dp[i]+dp[i+1]},0≤i≤n+1
• d p 1 [ i ] = s u m [ i ] ? 2 × m i n { s u m [ j ] } dp1[i] = sum[i] - 2 \times min\{sum[j]\} dp1[i]=sum[i]?2×min{ sum[j]}，其中sum[i]表示1～i个元素的前缀和，$1\le j\le i$
• dp2[i]类似，只不过从尾到头求解

我们可以 先求出前缀和sum[i]，后面就可以线性解决

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;const int maxn = 100000 + 10, inf = 1 << 30;
int sum[maxn], dp1[maxn], dp2[maxn], a;
int n;int main()
{
    scanf("%d", &n);for (int i = 1; i <= n; i++){
    scanf("%d", &a);sum[i] += sum[i-1] + a;}// dp1[i]记录前缀最大值int maxs = -inf;for (int i = 1; i <= n; i++){
    maxs = max(maxs, -2 * sum[i]);dp1[i] = sum[i] + maxs;}// dp2[i]记录后缀最大值maxs = -inf;for (int i = n; i > 0; i--){
    maxs = max(maxs, -2 * (sum[n] - sum[i-1]));dp2[i] = sum[n] - sum[i-1] + maxs;}maxs = sum[n];for (int i = 0; i <= n; i++){
    maxs = max(maxs, dp1[i] + dp2[i+1]);}printf("%d\n", maxs);return 0;
}

算法二

设操作的前缀和是$S_1$，后缀和是$S_2$，中间未操作数之和是$S_3$，整个序列原始之和是$S$
那么题目所求就是$?(S_1+S_2)+S_3$的值
由于$S_1+S_2=S?S_3$
因此$?(S_1+S_2)+S_3=2S_3?S$，而$S$是个定值，因此只要求$S_3$的最大值，也就是连续序列之和最大，这是“最大连续子序列之和”问题，这一般用$O(n)$的贪心算法解决：tmp表示当前是否要累加a[i]，sum表示当前累加到a[i]时和，那么当tmp<0时，不要累加a[i]，而只要tmp>=0都可以累加到sum中去

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;int main()
{
    int n, sum = 0, maxsum = 0, a, tmp = 0;scanf("%d", &n);for (int i = 0; i < n; i++){
    scanf("%d", &a);sum += a, tmp += a;if (tmp < 0){
    tmp = 0;} else {
    maxsum = max(maxsum, tmp);}}printf("%d\n", 2 * maxsum -  sum);return 0;
}