はじめに 最近累積和を覚えたのでメモを書き記そうと思います。 Qiitaだけではなく様々なサイトにやり方は掲載されています。しかし、解説者によってそれぞれ自分に合う説明合わない説明があると思うのでこの記事で誰か一人でも理解できた方がいれば嬉しく思います。 また、この記事は初歩の初歩しか説明しません。 累積和っていつ使うの? 例えば、こんな問題。 Q.9個の自然数が与えられる。その中で連続する3つの和の最大値を求めよ 例えば10個の自然数が「1,2,3,4,5,6,7,8,9」のような昇順だった場合、最後の3つを出力すればいいので計算量はO(1)でいいでしょう。しかし、「1,6,3,8,4,2,9,5,7」のようにバラバラだった場合、累積和を知らないあなただったらどうしますか? ※しゃくとり法を知ってる方は次の章まで読み進めて下さい。 僕だったらこうして全探索してました。(配列のインデックス