D - 徘徊

得分: $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$

输出

输出机器人从开始到结束过程中所占用的最大坐标。

3
2 -1 -2

5

机器人移动如下:

• 向正方向移动 $2$，到达坐标 $2$。
• 向正方向移动 $2$，到达坐标 $4$。然后向正方向移动 $-1$，到达坐标 $3$。
• 向正方向移动 $2$，到达坐标 $5$。然后向正方向移动 $-1$，到达坐标 $4$。然后向正方向移动 $-2$，到达坐标 $2$。

过程中所占用的最大坐标是 $5$，因此我们应输出 $5$。

5
-2 1 3 -1 -1

2

5
-1000 -1000 -1000 -1000 -1000

0

在这种情况下，初始坐标 $0$ 是所占用的最大坐标。