[At Coder] Solve the ABC182 D problem with Ruby


AtCoder Beginner Contest 182

D - Wandering

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
    if position + max_move > max_pos
        max_pos = position + max_move
    position += total_move

puts max_pos

Recommended Posts

[At Coder] Solve the ABC183 D problem with Ruby
[At Coder] Solve the ABC182 D problem with Ruby
Solve with Ruby AtCoder ABC177 D UnionFind
[Competition Pro] Solve the knapsack problem with Ruby
AtCoder ABC127 D hash to solve with Ruby 2.7.1
[Beginner] Let's solve AtCoder problem with Ruby while looking at the article!
Solve the N + 1 problem with Ruby on Rails: acts-as-taggable-on
I tried to solve the problem of "multi-stage selection" with Ruby
[At Coder] Introducing Competitive Pro with Ruby
I tried to solve the tribonacci sequence problem in Ruby, with recursion.
Solving with Ruby and Crystal AtCoder ABC 129 D
atcoder ABC70 D problem
Solving with Ruby and Java AtCoder ABC129 D 2D array
Solve the Discrete Logarithm Problem with an arbitrary mod
Solve Google problems with Ruby
Let's solve the FizzBuzz problem!
[Ruby] problem with if statement
Solving with Ruby, Perl and Java AtCoder ABC 136 D Breadth-first search
Programming with ruby (on the way)
Solve ARC104 D Multiset Mean with Scala, Java, C ++, Ruby, Perl, Elixir
Solving the knapsack problem with dynamic programming
I tried to solve the tribonatch sequence problem in Ruby (time limit 10 minutes)
Ruby problem ⑦
[Ruby] Define the hierarchy at the same time as Hash initialization with tap method
Manage the version of Ruby itself with rbenv
[Ruby] Exclude duplicate elements with the uniq method.
A quick look at the Monty Hall problem
Determine the current page with Ruby on Rails
To get Ruby Silver at the last minute
[Java] Try to solve the Fizz Buzz problem
Finding pi with the Monte Carlo method? (Ruby)
I checked the number of taxis with Ruby