/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 900 点
問題文
joisinoお姉ちゃんは、N 項から成る式、A_1 op_1 A_2 ... op_{N-1} A_N を持っています。
ここで、A_i は整数で、op_i は、+ または - の記号です。
joisinoお姉ちゃんは大きい数が好きなので、括弧を好きな数だけ( 0 個でもよい)挿入することで、計算の順番を変え、式の値を最大化したいです。
開き括弧は数の直前、閉じ括弧は数の直後にのみ、挿入することが許されます。
同じ場所に挿入する括弧の個数に制限はありません。
あなたの仕事は、式に括弧をいくつか挿入した際に、式の値としてありうるものの最大値を求めるプログラムを作ることです。
制約
- 1≦N≦10^5
- 1≦A_i≦10^9
- op_i は、
+または-の記号である。
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 op_1 A_2 ... op_{N-1} A_N
出力
括弧をいくつか挿入してできる式の値としてありうるものの最大値を出力せよ。
入力例 1
3 5 - 1 - 3
出力例 1
7
5 - (1 - 3) = 7 となり、これが最大なので、7 を出力します。
入力例 2
5 1 - 2 + 3 - 4 + 5
出力例 2
5
1 - (2 + 3 - 4) + 5 = 5 となり、これが最大なので、5 を出力します。
入力例 3
5 1 - 20 - 13 + 14 - 5
出力例 3
13
1 - (20 - (13 + 14) - 5) = 13 となり、これが最大なので、13 を出力します。
Score : 900 points
Problem Statement
Joisino has a formula consisting of N terms: A_1 op_1 A_2 ... op_{N-1} A_N.
Here, A_i is an integer, and op_i is an binary operator either + or -.
Because Joisino loves large numbers, she wants to maximize the evaluated value of the formula by inserting an arbitrary number of pairs of parentheses (possibly zero) into the formula.
Opening parentheses can only be inserted immediately before an integer, and closing parentheses can only be inserted immediately after an integer.
It is allowed to insert any number of parentheses at a position.
Your task is to write a program to find the maximum possible evaluated value of the formula after inserting an arbitrary number of pairs of parentheses.
Constraints
- 1≦N≦10^5
- 1≦A_i≦10^9
- op_i is either
+or-.
Input
The input is given from Standard Input in the following format:
N
A_1 op_1 A_2 ... op_{N-1} A_N
Output
Print the maximum possible evaluated value of the formula after inserting an arbitrary number of pairs of parentheses.
Sample Input 1
3 5 - 1 - 3
Sample Output 1
7
The maximum possible value is: 5 - (1 - 3) = 7.
Sample Input 2
5 1 - 2 + 3 - 4 + 5
Sample Output 2
5
The maximum possible value is: 1 - (2 + 3 - 4) + 5 = 5.
Sample Input 3
5 1 - 20 - 13 + 14 - 5
Sample Output 3
13
The maximum possible value is: 1 - (20 - (13 + 14) - 5) = 13.