← 返回题目列表

AtCoder · arc066_c

E. 加法和减法硬

中文机器翻译题面 查看原题

分数: 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.