AT_abc182_d [ABC182D] Wandering

题目描述

给定一个数列 $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, \dots, A_N$。

请你求出从操作开始到结束，机器人在所有时刻所能到达的最大坐标值。

输入格式

输入以以下格式从标准输入给出。

$N$
$A_1\ A_2\ A_3\ \dots\ A_N$

输出格式

输出机器人在操作过程中所能到达的最大坐标值。

样例 1

输入

3
2 -1 -2

输出

5

样例 2

输入

5
-2 1 3 -1 -1

输出

2

样例 3

输入

5
-1000 -1000 -1000 -1000 -1000

输出

0

说明/提示

数据范围

• $1 \leq N \leq 200000$
• $-10^8 \leq A_i \leq 10^8$
• 输入均为整数

样例解释 1

机器人按如下方式移动：

• 向正方向前进 $2$，坐标变为 $2$。
• 再向正方向前进 $2$，坐标变为 $4$，再向正方向前进 $-1$，坐标变为 $3$。
• 再向正方向前进 $2$，坐标变为 $5$，再向正方向前进 $-1$，坐标变为 $4$，再向正方向前进 $-2$，坐标变为 $2$。
  在整个操作过程中，坐标的最大值为 $5$，因此输出 $5$。

样例解释 3

在这种情况下，机器人最初所在的坐标 $0$ 就是最大值。

由 ChatGPT 4.1 翻译