← 返回题目列表

AtCoder · arc194_a

A. 堆栈上的操作

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

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