Submission #1218252

---

Source Code Expand

// In the name of Allah
// #Isart

#include<bits/stdc++.h>

#define pii pair<int, int>
#define pb push_back
#define F first
#define S second
#define ll long long
#define ld long double

using namespace std;

const int MAXN = 1e5 + 10;
ll a[MAXN], dp[MAXN], ps[MAXN];
int r[MAXN];

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	
	int n, s = 1;
	cin >> n;
	
	for(int i = 0; i < n; i ++){
		char ch = '+';
		if(i) cin >> ch;
		if(ch == '+') s = 1;
		else s = -1;
		cin >> a[i];
		a[i] *= s;
	}	
	for(int i = n - 1; i > -1; i --)
		ps[i] = ps[i + 1] + abs(a[i]);

	for(int i = n - 1; i > -1; i --){
		if(a[i] > 0 and a[i + 1] <= 0) r[i] = i;
		else r[i] = r[i + 1];
	}

	for(int i = n - 1; i > -1 ; i --){
		if(a[i] >= 0) dp[i] = dp[i + 1] + a[i];
		else if(a[i] < 0 and a[i + 1] < 0)
			dp[i] = a[i] + ps[i + 1];
		else if(a[i] < 0 and a[i + 1] > 0)
			dp[i] = max(a[i] + dp[i + 1], 2 * ps[r[i] + 1] - ps[i]);
		
	}
	cout << dp[0] << endl;

//	system("pause");
	return 0;	
}

Submission Info

Judge Result