Overview

Given \(N\) days of temperature data, the problem asks to compute the sum of every consecutive \(K\)-day window, then find the difference between the “maximum” and “minimum” among those sums.

Analysis

Naive Approach (Brute Force Calculation)

What happens if, for each \(i\), we compute \(S_i = A_i + A_{i+1} + \dots + A_{i+K-1}\) by summing \(K\) elements each time? Computing a single sum takes \(O(K)\) time, and there are \(N-K+1\) such sums, so the overall time complexity is \(O(N \times K)\). Looking at the constraints, \(N, K \leq 10^5\), so in the worst case we would need approximately \(10^{10}\) operations, which will not fit within the time limit (resulting in TLE).

Efficient Approach (Sliding Window)

When computing sums of consecutive intervals, notice that adjacent intervals \(S_i\) and \(S_{i+1}\) share most of their elements.

• \(S_i = \color{red}{A_i} + \underbrace{A_{i+1} + \dots + A_{i+K-1}}_{\text{common part}}\)
• \(S_{i+1} = \underbrace{A_{i+1} + \dots + A_{i+K-1}}_{\text{common part}} + \color{blue}{A_{i+K}}\)

From this relationship, we can see that the next sum \(S_{i+1}\) can be obtained from the current sum \(S_i\) by simply “subtracting the leftmost element \(A_i\)” and “adding the new rightmost element \(A_{i+K}\)”. $\(S_{i+1} = S_i - A_i + A_{i+K}\)\( This way, computing each new sum requires only 2 operations (one addition and one subtraction), making the overall time complexity \)O(N)$.

Algorithm

1. Compute the sum of the first \(K\) days \(S_1\), and set it as the tentative max_sum and min_sum.
2. Slide the window one position to the right at a time, repeating the following operations for \(i = 1\) to \(N-K\):
   • Subtract \(A_i\) from the current sum and add \(A_{i+K}\) to update the new sum.
   • Update max_sum and min_sum with the updated sum.
3. Finally, output max_sum - min_sum.

Complexity

• Time Complexity: \(O(N)\)
  • The initial sum computation takes \(O(K)\), and the subsequent sliding takes \(O(N-K)\), so the overall complexity is \(O(N)\). This is fast enough even for \(N=10^5\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the \(N\) temperature values in a list.

Implementation Notes

• Initial Value Setting: By setting the initial values of max_sum and min_sum to the first computed sum \(S_1\), we can correctly begin the comparisons.

• Loop Range: When discarding the \(i\)-th element (0-indexed), the next element entering the window is the \((i+K)\)-th element. Care must be taken with the loop’s end condition to avoid out-of-bounds index access.

• Fast Input: When handling input of size \(10^5\) in Python, reading all input at once using sys.stdin.read().split() is faster than calling input() repeatedly.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、スペースで分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 観測日数, K: 連続日数
    n = int(input_data[0])
    k = int(input_data[1])
    # A: 各日の気温
    a = list(map(int, input_data[2:]))

    # 最初の K 日間の合計値を計算する (S_1)
    current_sum = sum(a[:k])
    max_sum = current_sum
    min_sum = current_sum

    # スライディングウィンドウを用いて、連続する K 日間の合計値を順次計算する
    # S_{i+1} = S_i - A_i + A_{i+K}
    for i in range(n - k):
        current_sum = current_sum - a[i] + a[i + k]
        
        # 合計値の最大値と最小値を更新する
        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__':
    solve()

This editorial was generated by gemini-3-flash-thinking.