← 返回题目列表

AtCoder · abc182_d

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

输出

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


示例输入 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 是占用的最大坐标。