概要

連続する \(K\) 日間の気温の合計値の中で最大値と最小値の差を求める問題。

考察

この問題では、すべての連続する \(K\) 日間の気温の合計値を計算し、その中の最大値と最小値の差を求める必要があります。

素朴な方法では、各開始位置 \(i\) について、 \(S_i = A_i + A_{i+1} + \dots + A_{i+K-1}\) を愚直に計算することで、時間計算量は \(O(N \cdot K)\) となります。しかし、制約では \(N\) や \(K\) が最大で \(10^5\) まで取り得るため、この方法では全体で最大 \(10^{10}\) 回程度の計算が必要となり、実行時間制限（およそ数秒）内で処理しきれません（TLE）。

そこで、効率的な方法として「スライディングウィンドウ」技法が有効です。これは、一つ前の区間和から、端の要素を一つずつ入れ替えることで次の区間和を高速に求めることができる手法です。

たとえば、以下のような入力を考えます：

N = 5, K = 3
A = [1, 2, 3, 4, 5]

最初の区間和 \(S_1 = 1 + 2 + 3 = 6\) がわかっているとします。次に、区間を右に1つずらして \(S_2 = 2 + 3 + 4\) を求めたい場合、左端の \(1\) を引いて、右端に新たに \(4\) を足すだけで計算できます：

\[ S_2 = S_1 - A_1 + A_4 = 6 - 1 + 4 = 9 \]

このように差分で更新することで、各区間和を \(O(1)\) で求めることができ、全体の計算量を \(O(N)\) に抑えることができます。

この方法を使えば、すべての区間和の最大値と最小値を保持しながら更新していくことができ、最後に差を出力すれば答えが得られます。

アルゴリズム

1. 最初の \(K\) 項の和 \(S_1\) を計算し、これを current_sum とする。
2. max_sum と min_sum を current_sum で初期化。
3. 次の区間から順番に、差分を使って和を更新：
   • current_sum = current_sum - A[i - 1] + A[i + K - 1]
4. 更新された current_sum で max_sum と min_sum を更新。
5. 最後に max_sum - min_sum を出力。

計算量

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

実装のポイント

• 区間和の更新は差分で行い、毎回 \(K\) 個の和を計算しないようにする。
• 最初の和の計算後、ループでインデックスエラーにならないよう注意する（range(1, N - K + 1)）。
• 最大・最小値の更新は毎回行い、漏れなく比較する。

## ソースコード

```python
from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

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

    # スライディングウィンドウ
    for i in range(1, N - K + 1):
        # 差分で和を更新
        current_sum = current_sum - A[i - 1] + A[i + K - 1]
        if current_sum > max_sum:
            max_sum = current_sum
        if current_sum < min_sum:
            min_sum = current_sum

    print(max_sum - min_sum)

if __name__ == "__main__":
    main()

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