最初の時点で0人乗っていたとしてシミュレーションします。

もしシミュレーションの過程でバスに乗っている人数が負になった場合、”実はバスにはもっと人が乗っていた”と思うことで、その時点でバスに乗っている人数は0だったことにします。

例えば \(A=(1,-2,2,-1,-2,3)\) のときシミュレーションは次のように進行します：

• 最初、バスに乗っている人数は0である
• 1人乗ってきて、バスに乗っている人数は1になる
• 2人降りて、バスに乗っている人数は-1になってしまう。”実はバスにはもっと人が乗っていた”ことにして、バスに乗っている人数は0になったことにする
• 2人乗ってきて、バスに乗っている人数は2になる
• 1人降りて、バスに乗っている人数は1になる
• 2人降りて、バスに乗っている人数は-1になってしまう。”実はバスにはもっと人が乗っていた”ことにして、バスに乗っている人数は0になったことにする
• 3人乗ってきて、バスに乗っている人数は3になる

このようにして最後までシミュレーションし終えたときの人数が答えです。なぜなら、これ以上人数を減らすと”実はバスにはもっと人が乗っていた”を最後に発動したタイミングの人数が負になってしまうためです。

実装例(Python)

input()
crr=0
for a in map(int,input().split()):
  crr=max(crr+a,0)
print(crr)