/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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 進み、\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 が最大値です。
Score : 400 points
Problem Statement
Given is a number sequence A_1, A_2, A_3, \dots, A_N, which may contain negative elements.
On a number line, there is a robot at coordinate 0. It will do the following actions in order:
- Move A_1 in the positive direction.
- Move A_1 in the positive direction, and then move A_2 in the positive direction.
- Move A_1 in the positive direction, then move A_2 in the positive direction, and then move A_3 in the positive direction.
\hspace{140pt} \vdots
- Move A_1 in the positive direction, then move A_2 in the positive direction, then move A_3 in the positive direction, \ldots, \dots, and then move A_N in the positive direction.
Find the greatest coordinate occupied by the robot from the beginning to the end of the process.
Constraints
- 1 \le N \le 200000
- -10^8 \le A_i \le 10^8
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N
Output
Print the greatest coordinate occupied by the robot from the beginning to the end of the process.
Sample Input 1
3 2 -1 -2
Sample Output 1
5
The robot moves as follows:
- Move 2 in the positive direction, to coordinate 2.
- Move 2 in the positive direction, to coordinate 4. Then move -1 in the positive direction, to coordinate 3.
- Move 2 in the positive direction, to coordinate 5. Then move -1 in the positive direction, to coordinate 4. Then move -2 in the positive direction, to coordinate 2.
The greatest coordinate occupied during the process is 5, so we should print 5.
Sample Input 2
5 -2 1 3 -1 -1
Sample Output 2
2
Sample Input 3
5 -1000 -1000 -1000 -1000 -1000
Sample Output 3
0
In this case, the initial coordinate 0 is the greatest coordinate occupied.