題目描述

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;
}