スライド窓の最大和
スライド窓の最大和
このレッスンで分かること
- アルゴリズムを 1 段階速くするだけで、扱えるデータサイズが 3 桁 違ってくる
- 素朴な実装では、
i = 0..n-kのループで毎回内側でk個をsumし直すため計算量はO(n * k)になります- 整数配列
arrと窓のサイズkが与えられたとき、arrの 連続する K 個の要素 の和のうち最大値を求めたい
スライド窓の最大和 とは
長さ
kの連続部分配列の和の最大値を、毎回足し直さずに 窓を 1 つずらす ことでO(n)に落とすスライディングウィンドウを学ぶ。
整数配列 arr と窓のサイズ k が与えられたとき、arr の 連続する K 個の要素 の和のうち最大値を求めたい。これは「スライディングウィンドウ (sliding window)」と呼ばれる頻出パターンの代表例です。
素朴な実装では、i = 0..n-k のループで毎回内側で k 個を sum し直すため計算量は O(n * k) になります。n も k も大きくなると無視できないコストです。スライド窓は、この計算を O(n) に落とす定石です。
「窓のサイズが固定」「連続部分」を見たら、毎回足し直さず差分更新できないかを考える。これが線形時間化の鍵。
差分更新の発想
窓を 1 つ右にずらすとき、抜けるのは 左端の要素 arr[i-1]、増えるのは 新しい右端 arr[i+k-1] だけです。残りの k-2 個は前回と同じなので、わざわざ全部足し直す必要はありません。
図のポイント (テキスト併記)
- つまり次のような関係式が成り立ちます
つまり次のような関係式が成り立ちます。
windowSum_next = windowSum - arr[left] + arr[right]- 各ステップで定数時間 (
O(1)) で更新できる - 全体の計算量は
O(n)
Python での実装
Python
def maxWindowSum(arr, k):
if k <= 0 or len(arr) < k:
return 0
windowSum = sum(arr[:k])
best = windowSum
for i in range(k, len(arr)):
windowSum += arr[i] - arr[i - k]
if windowSum > best:
best = windowSum
return best最初の k 要素の和を windowSum に入れ、それを起点にスライドしていきます。arr[i] - arr[i - k] の 1 行で、入れ替えと差分計算を同時に行えるのがポイントです。
JavaScript での実装
JavaScript
function maxWindowSum(arr, k) {
if (k <= 0 || arr.length < k) return 0;
let windowSum = 0;
for (let i = 0; i < k; i++) windowSum += arr[i];
let best = windowSum;
for (let i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k];
if (windowSum > best) best = windowSum;
}
return best;
}ロジックは Python と完全に同じです。arr.length < k の早期 return を忘れると、窓のサイズが配列より大きい場合に誤った結果が出ます。
計算量の比較
素朴な二重ループ版と比較してみましょう。
- 素朴版: 外ループ
n-k+1回 × 内ループk回 =O(n * k) - スライド窓: 初期化
O(k)+ 残りO(n - k)=O(n)
n = 10^6、k = 10^3 のように大きくなると、素朴版は 10^9 回程度の演算が必要になり時間切れになります。スライド窓なら 10^6 回で終わります。
アルゴリズムを 1 段階速くするだけで、扱えるデータサイズが 3 桁 違ってくる。これが計算量を意識する価値。
よくある間違い
1 つ目は for i in range(k, len(arr)) の境界を len(arr) - k + 1 などにしてしまうケースです。スライドの開始は i = k (新しい右端のインデックス) で良く、終わりは i = len(arr) - 1 までです。
2 つ目は windowSum += arr[i]; windowSum -= arr[i - k] を別行で書くこと自体は問題ありませんが、順序を間違えて先に引いて足す とインデックスがずれる落とし穴があります。差分は 1 行にまとめて arr[i] - arr[i - k] で書くのが安全です。
3 つ目は 負の値 を含むケースで初期値を 0 にしてしまうことです。最大値の初期値は 最初の窓の和 か、あるいは -Infinity 相当の値にすべきです。
やってみよう
[1, 3, 2, 6, -1, 4, 1, 8, 2]、k = 5で手計算してみる。[3, 2, 6, -1, 4]の和 14、[2, 6, -1, 4, 1]の和 12、[6, -1, 4, 1, 8]の和 18、[-1, 4, 1, 8, 2]の和 14 と続くので、最大は[6, -1, 4, 1, 8]の和 18 になります。- 窓のサイズを 1 にしたら、結果は
max(arr)と一致するかを確認する。 - 同じテクニックで「窓内の 平均 の最大値」を求める関数も書いてみる。
スライディングウィンドウは「連続区間」+「固定サイズ」+「集約値の更新」の三拍子。差分更新の発想に慣れれば一気に解ける問題が増える。
よくある質問
Q. スライド窓と二重ループはどう違う？
A. スライド窓は窓のサイズや内容を逐次更新するため O(n) で済みます。二重ループ O(n²) と比較して、配列が長くなるほど差が顕著になります。「連続区間の最大和」「重複なし最長部分文字列」など、連続部分列の問題で定番のテクニックです。
Q. 窓の縮め方が分からなくなります
A. 「条件を満たす最短/最長の窓」を探すなら、右端を伸ばし続け条件違反になったら左端を縮める形が定石です。while (条件違反) left++; のループで縮めるパターンを覚えると応用が効きます。LeetCode の Minimum Window Substring が典型例です。
Q. 可変サイズと固定サイズの違いは？
A. 固定サイズは k 個の連続要素を見るとき（移動平均）、可変サイズは条件を満たす最長/最短の連続部分を探すとき（最長 unique 文字列）に使います。実装は両方似ていますが、終了条件の書き方で微妙に異なるため両方の典型例を押さえると安心です。
次のレッスン
次は 回文判定 で、回文判定 を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- スライド窓 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. スライド窓 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 1 <= k <= len(arr) であると仮定して良い
- 計算量は O(n) であること (素朴な O(n*k) は不可)
- 戻り値は窓内の最大の和 (整数) であること
入出力例
test-cases.txt
maxWindowSum([1,2,3,4,5], 2) → 9
maxWindowSum([1,2,3,4,5], 3) → 12
maxWindowSum([5,1,1,1,5], 2) → 6
maxWindowSum([2,3,4,1,5], 1) → 5
maxWindowSum([1,3,2,6,-1,4,1,8,2], 5) → 18
maxWindowSum([-1,-2,-3,-4], 2) → -3
maxWindowSum([7], 1) → 7