Python3で解く AtCoder Beginner Contest 182 D - Wandering

制約上、愚直にやるとTLE。累積和を２つ持つ必要がある。イメージさえできれば、コードはすっきりできる。

概要

整数列 $A$ が与えられる。
以下のように座標を進む。( $A_i$ )が正なら右へ負なら左へ進むイメージ）
最初は0
$A_1$
$A_1, A_2$
$A_1, A_2, A_3$
...
$A_1, A_2, A_3, ..., A_n$
この時に、一番大きく進んだ時の座標位置はどこ？

解くときに考えた内容

$A$ のi番目までの累積和（a_cumとする）を求める。
その中で最も大きい値を保持する（maxv）とする。
番目までの行動が終了した時の座標をall_cumとする
- でもこの処理は一番最後に行い、現在の座標は $i-1$ 番目までの行動が終了した時の座標を用いる。（つまりindexをずらして足算する）

f:id:black_tank_top:20201109071143j:plain — 最大の位置の求め方のイメージ図

この時全ての和と言っているのはall_cumで累積和の累積和（ただしmaxvを求めているiの一つ前の値）としている。最後は $A$ の $A_{n-1}$ までの三角をぜーんぶ足した物と $A_1$ から $A_n$ の中での最大の値の合計が、これまでの最大位置よりも大きいかを比べることになる。

f:id:black_tank_top:20201109071128j:plain — 最後の処理のイメージ

コード

n = int(input())
a = [int(x) for x in input().split()]
ans = 0
all_cum = 0
maxv = 0
a_cum = 0
for i in range(n):
    # i番目までの累積和
    a_cum += a[i]
    # i番目までの累積和で最も大きい値
    maxv = max(maxv, a_cum)
    # この段階ではall_cumはi-1番目までに手順の累積和
    ans = max(ans, all_cum+maxv)
    # ここでall_cumはi番目までに手順の累積和
    all_cum += a_cum
print(ans)

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。