分数: 400 点
问题陈述
给定的是一个数字序列 A_1, A_2, A_3, \dots, A_N,其中可能包含负面元素。
在数轴上,坐标处有一个机器人 0。它将按顺序执行以下操作:
- 移动 A_1 正方向。
- 移动 A_1 正方向,然后移动 A_2 正方向。
- 移动 A_1 正方向,然后移动 A_2 正方向,然后移动 A_3 正方向。
\hspace{140pt} \vdots
- 移动 A_1 正方向,然后移动 A_2 正方向,然后移动 A_3 正方向, \ldots, \dots,然后移动 A_N 正方向。
求机器人从过程开始到结束所占据的最大坐标。
约束
- 1 \le N \le 200000
- -10^8 \le A_i \le 10^8
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N
输出
打印机器人从过程开始到结束所占用的最大坐标。
示例输入 1
3 2 -1 -2
示例输出 1
5
机器人移动如下:
- 移动 2 正方向,协调 2.
- 移动 2 正方向,协调 4。然后移动 -1 正方向,协调 3.
- 移动 2 正方向,协调 5。然后移动 -1 正方向,协调 4。然后移动 -2 正方向,协调 2.
过程中占用的最大坐标为 5,所以我们应该打印 5.
示例输入 2
5 -2 1 3 -1 -1
示例输出 2
2
示例输入 3
5 -1000 -1000 -1000 -1000 -1000
示例输出 3
0
在这种情况下,初始坐标 0 是占用的最大坐标。