分数: 400 点
问题陈述
给你一个长度的整数序列 N: (A_1, A_2, \ldots, A_N)。还有一个顺序 S,最初是空的。
对于每个 i = 1, 2, \ldots, N 按照此顺序,您只需执行以下两个操作之一:
- 追加 A_i 作为结尾的元素 S.
- 删除最后一个元素 S。如果出现以下情况,则不能选择此操作 S 为空。
打印元素总和的最大可能值 S 完成所有操作后。
约束
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq A_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印答案。
示例输入 1
6 3 -1 -4 5 -9 2
示例输出 1
8
从初始状态开始,其中 S 是一个空序列,考虑以下操作:
- 对于 i = 1,追加 A_1 = 3 到年底 S。现在, S = (3).
- 对于 i = 2,追加 A_2 = -1 到年底 S。现在, S = (3, -1).
- 对于 i = 3,删除最后一个元素 S。现在, S = (3).
- 对于 i = 4,追加 A_4 = 5 到年底 S。现在, S = (3, 5).
- 对于 i = 5,追加 A_5 = -9 到年底 S。现在, S = (3, 5, -9).
- 对于 i = 6,删除最后一个元素 S。现在, S = (3, 5).
这里,元素的总和 S 在所有操作之后是 3 + 5 = 8,这是最大可能值。
示例输入 2
1 -1
示例输出 2
-1
请注意,如果 S 为空,您必须选择追加一个元素。
示例输入 3
20 -14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16
示例输出 3
369