Given the sequence $ A_1, A_2, A_3, ..., A_N $. This sequence may contain negative elements. The robot located at the coordinate $ 0 $ on the number line performs the following operations in order.

Go forward $ A_1 $ in the positive direction. Advance $ A_1 $ in the positive direction and $ A_2 $ in the positive direction. Forward $ A_1 $ in the positive direction, $ A_2 $ in the positive direction, and $ A_3 $ in the positive direction. ⋮ Forward $ A_1 $ in the positive direction, $ A_2 $ in the positive direction, $ A_3 $ in the positive direction, $ ... $, $ A_N $ in the positive direction.

Find the maximum value of the robot coordinates from the start to the end of the operation.

1≦N≦200000 -10^8≦A_i≦10^8 All inputs are integers

N A_1 A_2 A_3 ... A_N

```
n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)
#Coordinates of the robot after operation
position = 0
#Amount of movement due to movement
total_move = 0
#Maximum value of coordinates from start to end when the operation starts at coordinate 0
max_move = 0
#Maximum value of robot coordinates
max_pos = 0
a.each do |move|
total_move += move
if total_move > max_move
max_move = total_move
end
if position + max_move > max_pos
max_pos = position + max_move
end
position += total_move
end
puts max_pos
```

Recommended Posts