【AtCoder Regular Contest 066 E】Addition and Subtraction Hard | Mrsrz's blog

贪心。

题目大意：

给定 $n$ 个数，中间有 $n-1$ 个 + 号或者 - 号。

现在要给式子套上括号，使得最终结果最大。求最大结果。

题解：

在 + 号后面套括号显然是没有意义的，所以括号只在 - 号后面。

考虑在一个 - 号后面套括号以后，里面原来贡献为负的贡献变为正了，原来贡献为正的贡献变为负了（第一个数的贡献仍为负）。

那么，我们考虑括号后面第一个由 + 号连接的连通块。这个连通块的贡献无论如何都是负。然后后面所有的数的贡献，我们都可以让它为正：如果是负号，则其本身就会被纠正为正的；如果是 + 号连通块，则连通块前面必然有一个 - 号，那么给这个连通块加上括号之后，这个连通块的贡献就会再次反转，变为正。

所以我们只需要枚举外层括号的左端点的位置，然后用前后缀和计算即可。

时间复杂度 $O(n)$。

Code：

#include<cstdio>
typedef long long LL;
const int N=1e5+8;
int A[N],op[N],n,nxt[N],nx;
LL ans,now,suf[N];char s[4];
int main(){
    scanf("%d%d",&n,A+1),ans=A[1];
    for(int i=2;i<=n;++i)scanf("%s%d",s,A+i),ans+=A[i]*((op[i]=*s=='-')?-1:1);
    for(int i=n;i;--i){
        suf[i]=suf[i+1]+A[i];
        if(op[i])nxt[i]=nx,nx=i;
    }
    now=A[1];
    for(int i=2;i<=n;++i){
        if(op[i]&&nxt[i]){
            LL nw=now-suf[i]+2*suf[nxt[i]];
            if(nw>ans)ans=nw;
        }
        now+=A[i]*(op[i]?-1:1);
    }
    printf("%lld\n",ans);
    return 0;
}