分数: 900 点
问题陈述
Joisino 的公式如下: N 条款: A_1 op_1 A_2 ... op_{N-1} A_N。
在这里, A_i 是一个整数,并且 op_i 是一个二元运算符 + or -。
因为 Joisino 喜欢大数字,所以她希望通过在公式中插入任意数量的括号对(可能是零)来最大化公式的评估值。
左括号只能紧接在整数之前插入,右括号只能紧接在整数之后插入。
允许在一个位置插入任意数量的括号。
您的任务是编写一个程序,在插入任意数量的括号对后找到公式的最大可能评估值。
约束
- 1≦N≦10^5
- 1≦A_i≦10^9
- op_i 是
+or-.
输入
输入由标准输入按以下格式给出:
N
A_1 op_1 A_2 ... op_{N-1} A_N
输出
插入任意数量的括号对后,打印公式的最大可能评估值。
示例输入 1
3 5 - 1 - 3
示例输出 1
7
最大可能值为: 5 - (1 - 3) = 7.
示例输入 2
5 1 - 2 + 3 - 4 + 5
示例输出 2
5
最大可能值为: 1 - (2 + 3 - 4) + 5 = 5.
示例输入 3
5 1 - 20 - 13 + 14 - 5
示例输出 3
13
最大可能值为: 1 - (20 - (13 + 14) - 5) = 13.