【ABC182 D】「Wandering」を解く【Python3】

コンテスト一覧へ

 

数列Aiが与えられ、数直線上の座標0に置かれているロボットが、ある条件の動作を行った際に動画開始時から終了時までのロボットの座標の最大値を求める問題です。

提出
n = int(input())
a = list(map(int, input().split()))

b = 0
ans = 0
sum = 0
i_max = 0

for i in range(n):
    b += a[i]
    i_max = max(i_max, b)
    ans = max(ans, sum+i_max)
    sum += b

print(ans)

「正の向きにA1進む」「正の向きにA1進み、正の向きにA2進む」……と動作が増えていきます。

「正の向きにA1進み、……、正の向きにAi進む」という動作のみを考えたとき、座標が一番大きくなる場所は、累積和が一番大きいところです。

例えば、入力例2では、数列Aは[-2, 1, 3, -1, -1]となり、累積和は[-2, -1, 2, 1, 0]となります。

iが3以上であれば、最大の累積和は「2」となりますが、3以下までは異なります。

「b += a[i]」でその都度の累積和を求め、最大の累積和を「i_max」に入力します。

これに「sum」を足したものと、「ans」を比較して、大きい方を「ans」に代入します。

最後に「sum」に累積和を足して1回のループは終わりです。

(sumには「正の向きにA1進み、……、正の向きにAi進む」という動作を毎回足していることになります)

すべてループが終わった後、「ans」には座標の最大値が入っているので、これを出力します。

【ABC182】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。