スライド窓の最大和

窓をずらすたびに、全部を足し直している

連続した k 個の合計のうち、最大のものを知りたい。素直に書くと、窓の位置ごとに k 個を足し直します。5 日ぶんの売上で 3 日の窓なら、3 回の足し算を 3 か所で、合計 9 回です。窓を 30 日に広げれば、1 か所につき 30 回になります。

ここで、隣り合う 2 つの窓を並べてみてください。[4, 8, 2] の次は [8, 2, 9] です。8 と 2 は両方に入っています。足し直しているぶんのほとんどは、前回すでに足した数でした。

変わるのは両端の 2 つだけ

窓を 1 つ右へずらすと、抜けるのは左端の 1 つ、入るのは新しい右端の 1 つ。それ以外は変わりません。だから前回の合計から抜ける値を引き、入る値を足せば、それが次の合計です。

最初の窓だけは k 個を足す必要がありますが、そこから先は 1 か所につき引き算と足し算が 1 回ずつです。手間が窓の大きさに左右されなくなり、要素数だけで決まります。

[4, 8, 2, 9, 3] を最後まで動かすと、14 の次が 19、その次は 8 が抜けて 3 が入るので 14 です。最大は 19 でした。足し算の回数は、最初の 3 回と、その後の 2 か所ぶんで合計 7 回。素朴に足し直すと 9 回でした。

この差は入力が大きくなるほど開きます。100 万件のデータを 1,000 件の窓で見るなら、素朴なやり方は 10 億回、差分だけの更新なら 100 万回です。窓を広げても手間が変わらないというのが、この方法のいちばんの取り柄です。

抜ける値がどこにいるかを、上の例で確かめておきます。入れたのは 4 番目の sales[3]、抜けたのは 1 番目の sales[0]。差は 3 で、これは窓の大きさそのものです。窓が 3 つぶんの幅を持っているのだから、右端から 3 つ戻ったところがちょうど窓の外側の 1 つ手前になります。

ここを 1 つずらすと、まだ窓の中にいる値を引くか、すでに外へ出た値をもう一度引くことになります。合計が少しずつ狂うだけで例外は出ないので、小さな配列で手計算と突き合わせて確かめてください。

最大値の置き場所を 0 で始めない

最大値を覚える変数を 0 から始めると、すべて負の値の配列で 0 が返ります。どの窓の合計も 0 より小さいので、一度も更新されないからです。売上ではなく損益や気温を入れた瞬間に化けます。

置き場所の初期値は、最初の窓の合計にしてください。最初の窓は必ず存在するので、比較の土台としてこれ以上ふさわしい値はありません。

1. 1 <= k <= len(arr) であると仮定して良い
2. 計算量は O(n) であること (素朴な O(n*k) は不可)
3. 戻り値は窓内の最大の和 (整数) であること