题解：CF2274B Prefix
T_P_T_C
·
·
题解
题目传送门
题目描述
给定长为 N 一个数组 A，对于每一个 i 记 sum 为 A_1 到 A_{i-1} 的前缀和，你可以将 A_i 变成 A_i，A_i+sum，A_i-sum 中的其中一个，求操作完后整个数组的最大值。
解法描述
不难发现对于每一个 A_i，它对答案的贡献就是它进行三种操作过后的最大值。
如果选择 $A_i+sum$，那么 $sum$ 更大答案更优，反之亦然。
所以我们可以分别维护一个前缀最大值和一个前缀最小值，并在维护过程中统计答案。
顺带一提，稍微推一下柿子就可以发现维护 $sum$ 时 $sum$ 的取值也只有 $A_i$，$A_i+sum$，$A_i+sum\times2$ 这三种取值，所以维护过程中不会因为其他因素导致答案变劣。
时间复杂度 $O(N)$。
### AC Code
```cpp
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define int long long
#define endl '\n'
using namespace std;
int T,N,A[55];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T--)
{
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>A[i];
}
int sum=A[1],sum2=A[1],ans=A[1];
for(int i=2;i<=N;i++)
{
ans=max(ans,max({A[i]-sum,A[i],A[i]+sum2}));
sum=min({A[i],sum+A[i],sum*2+A[i]});
sum2=max({A[i],sum2+A[i],sum2*2+A[i]});
}
cout<<ans<<endl;
}
return 0;
}
```
那么完结撒花！