题目描述

There are n stores located along a street, numbered from 1 to n from nearest to farthest. Last month, the storek had a net profit of rk . If rk is positive, it represents a profit of rk dollars; if rk is negative, it represents a loss of −rk dollars.
As a master of business magic, you have two types of spells at your disposal that you can use to alter the net profits of these stores for the next month:

1. Blue Magic: You can choose a single continuous interval [L, R] . The effect of this spell will be to double the net profit of every store from store L to store R (inclusive) for the next month. That is, if k ∈ [L, R] , then storek will have net profit 2rk next month.
2. Green Magic: You can choose any store and cast the green magic on it. The effect of the green magic is to change the next month’s net profit of that store to the negative of its last month’s net profit.

Any store that has not been affected by either spell will have the same net profit next month as it did last month.
However, there are some restrictions when casting spells. You can only cast the blue magic once and it must be used before the green magic. Additionally, the green magic cannot be cast on any store that has already been affected by the blue magic. Your task is to determine the maximum possible sum of the net profits for all stores for the next month after casting your spells optimally.

输入

The first line contains an integern , the numberof stores. The second line contains n space-separated integers r1 , r2 , . . . , rn , where rk is the net profit of store k last month.

输出

Output a single integer, the maximum possible total net profit of all stores forthe next month aftercasting the spells optimally.

样例输入

【样例1】
5
-2 5 -3 4 -1
【样例2】
7
-1 -1 -1 -1 -1 -1 -1
【样例3】
4
998244353 864197532 -7 1000000000

样例输出

【样例1】
20
【样例2】
7
【样例3】
5724883756

提示

Technical Specification
• 1 ≤ n ≤ 3 × 
•  ≤ rk ≤  for k ∈ { 1, 2, . . . , n }

思路分析

prefix存储前缀和。

negat存储绝对值前缀和。

将最终结果ans初始化为negat[n]。（此为仅仅使用Green Magic的情况）

然后遍历R，寻找区间[L,R]，更新ans。

当使用Blue Magic，得到的结果为，整理之后得到。

在遍历R从1到n的过程中，顺便查找最小的，记为min_left，更新min_left，更新ans。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll ans;
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;vector<int>r(n+1);vector<ll>prefix(n+1,0);vector<ll>negat(n+1,0);for(int i=1;i<=n;i++){cin>>r[i];prefix[i]=prefix[i-1]+r[i];negat[i]=negat[i-1]+abs(r[i]);}ans=negat[n];ll min_left=LONG_MAX;for(int i=1;i<=n;i++){min_left=min(min_left,2*prefix[i-1]-negat[i-1]);ans=max(ans,prefix[i]*2+negat[n]-negat[i]-min_left);}cout<<ans;return 0;
}