概要

長さ \(N\) の配列 \(A\) から、連続する \(K\) 個の要素の和を最大にする区間を選び、その最大値を求める問題です。

考察

連続する \(K\) 本の木を選ぶと収穫量はその区間の合計 \(\sum A_i\) になります。したがって「長さ \(K\) の連続部分列の和の最大値」を求めればよいです。

素朴には、全ての開始位置 \(l\)（\(1 \le l \le N-K+1\)）について - 区間 \([l, l+K-1]\) の和を毎回 \(K\) 回足して計算

とすると、計算量は \((N-K+1)\times K\) で最悪 \(O(NK)\) になります。制約は \(N \le 2\times 10^5\) なので、例えば \(N=K=2\times 10^5\) のとき \(4\times 10^{10}\) 回程度の加算になり、時間内に終わりません（TLE）。

ここで重要な観察は、隣り合う区間の和は少しの更新で求められることです。
例えば区間を1つ右にずらすと、

• 前の区間: \(A_l + A_{l+1} + \cdots + A_{l+K-1}\)
• 次の区間: \(A_{l+1} + A_{l+2} + \cdots + A_{l+K}\)

なので、次の区間の和は「前の和から \(A_l\) を引いて、\(A_{l+K}\) を足す」だけで更新できます。

例：\(A=[3,1,4,1,5]\), \(K=3\)
最初の和は \(3+1+4=8\)。次の区間は \(8 - 3 + 1 = 6\)（\(1+4+1\)）のように \(O(1)\) で求まります。

この考え方（スライディングウィンドウ）を使うと全体を \(O(N)\) で処理できます。

アルゴリズム

スライディングウィンドウ（長さ固定の区間和の更新）を用います。

1. 最初の \(K\) 個の和 \(window\_sum = \sum_{i=1}^{K} A_i\) を計算し、これを暫定最大値 \(best\) とする。
2. \(i=K\) から \(N-1\)（0-indexed）まで順に、区間を1つ右へずらして
   • \(window\_sum \leftarrow window\_sum + A[i] - A[i-K]\) と更新する（右端を足して左端を引く）。
3. 各更新後に \(best = \max(best, window\_sum)\) を取る。
4. 最後に \(best\) を出力する。

計算量

• 時間計算量: \(O(N)\)（各要素を高々定数回ずつ処理）
• 空間計算量: \(O(1)\)（入力配列を除けば定数。※配列 \(A\) を保持する分は \(O(N)\)）

実装のポイント

• \(A_i\) が最大 \(10^9\)、\(K\) が最大 \(2\times 10^5\) なので和は最大で \(2\times 10^{14}\) 程度になります。Python の int は多倍長なのでそのままで安全です。

• ループは for i in range(K, N): とし、更新式を window_sum += A[i] - A[i - K] のように書くとミスが減ります。

• 入力が大きいので sys.stdin.buffer.readline を使うと安定して高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    window_sum = sum(A[:K])
    best = window_sum
    for i in range(K, N):
        window_sum += A[i] - A[i - K]
        if window_sum > best:
            best = window_sum
    print(best)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。