概要

一列に並んだ \(N\) 本の果物の木から、連続する \(K\) 本を選ぶことで得られる果物の個数の最大値を求めます。

考察

この問題では、連続する \(K\) 個の要素からなる部分列（部分配列）の和の最大値を求めることになります。

例えば、\(A = [1, 2, 3, 4, 5]\)、\(K = 3\) の場合、考えられる連続する3つの和は次のようになります： - \(A[0] + A[1] + A[2] = 1 + 2 + 3 = 6\) - \(A[1] + A[2] + A[3] = 2 + 3 + 4 = 9\) - \(A[2] + A[3] + A[4] = 3 + 4 + 5 = 12\)

この中で最大は \(12\) です。

愚直にすべての区間について和を計算すると、\(O(N \cdot K)\) の時間がかかります。\(N\) や \(K\) が最大で \(2 \times 10^5\) になるため、これは時間内に計算しきれません（TLE）。

そこで、効率的に連続する区間の和を求める方法として「スライディングウィンドウ（しゃくとり法の一種）」を使います。これは、一つ前の区間の和を利用して次の区間の和を高速に求めることができるテクニックです。

例えば、ある区間 \([i, i+K-1]\) の和が分かっていれば、次の区間 \([i+1, i+K]\) の和は： $\( \text{新しい和} = \text{古い和} - A[i] + A[i + K] \)$ と計算できます。

このようにして、各区間の和を \(O(1)\) で計算でき、全体で \(O(N)\) で解くことができます。

アルゴリズム

1. 最初の \(K\) 要素の和を計算し、これを現在の最大値とする。
2. その後、スライディングウィンドウの要領で、左端を1つずつ進めながら、区間和を更新していく。
3. 各ステップで、その区間和がこれまでの最大値より大きければ更新する。
4. 最終的な最大値を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力配列を除く）

実装のポイント

• 最初の区間和を計算するときに sum(A[:K]) を使うと簡潔に書けます。
• ループの範囲は range(1, N - K + 1) とすることで、正しいインデックスで処理できます。
• current_sum の更新時に、引き算と足し算の順序を間違えないように注意しましょう。

## ソースコード

```python
N, K = map(int, input().split())
A = list(map(int, input().split()))

# 最初のK個の和を計算
current_sum = sum(A[:K])
max_sum = current_sum

# スライディングウィンドウで最大値を更新
for i in range(1, N - K + 1):
    current_sum = current_sum - A[i - 1] + A[i + K - 1]
    max_sum = max(max_sum, current_sum)

print(max_sum)

この解説は qwen3-coder-480b によって生成されました。