Overview

Given temperature data over \(N\) days, the problem asks to compute the sum for every consecutive \(K\)-day period, then calculate the difference between the maximum and minimum of these sums. This can be solved efficiently using a sliding window technique.

Analysis

Naive Approach and Its Issues

The simplest method is to compute \(S_i = A_i + A_{i+1} + \dots + A_{i+K-1}\) for each \(i = 1, 2, \dots, N-K+1\) by summing \(K\) elements each time. In this case, computing each \(S_i\) takes \(O(K)\), resulting in an overall complexity of \(O((N-K+1) \times K)\). When \(N\) is up to \(10^5\), this becomes \(O(N^2)\) in the worst case, which risks TLE (Time Limit Exceeded).

Key Insight: Difference Between Adjacent Intervals

Focusing on two consecutive intervals, we can see that they largely overlap.

\[S_i = A_i + A_{i+1} + \dots + A_{i+K-1}\]

\[S_{i+1} = A_{i+1} + A_{i+2} + \dots + A_{i+K}\]

Taking the difference of these two:

\[S_{i+1} = S_i - A_i + A_{i+K}\]

In other words, if \(S_i\) is known, \(S_{i+1}\) can be obtained in \(O(1)\) by simply subtracting the first element and adding the new element at the end. This is the idea behind the sliding window technique.

Concrete Example

For \(N = 6, K = 3\) with temperature data [2, 5, 3, 7, 1, 4]:

The maximum is \(15\) and the minimum is \(10\), so the answer is \(15 - 10 = 5\).

Algorithm

1. Initialization: Compute the sum \(S_1\) of the first \(K\) elements, and set both the tentative maximum and minimum to \(S_1\).
2. Sliding: For \(i = 2, 3, \dots, N-K+1\), repeat the following:
   • Update the sum using \(S_i = S_{i-1} - A_{i-1} + A_{i+K-1}\).
   • Update the maximum and minimum.
3. Output: Output the difference between the maximum and minimum.

Complexity

• Time complexity: \(O(N)\) (the initial sum computation takes \(O(K)\), and the sliding takes \(O(N-K)\), which together is \(O(N)\))
• Space complexity: \(O(N)\) (needed to store array \(A\). Since the running sum is managed with a single variable, the additional space is \(O(1)\))

Implementation Notes

• There is no need to store all \(S_i\) values in an array. It is sufficient to manage the current sum with a single variable S and update it at each slide. This avoids using extra memory.

• By incrementally updating the maximum and minimum, the answer can be obtained in a single pass through the loop.

• Pay attention to loop indices. In S += A[i + K - 1] - A[i - 1], it is important to correctly set the indices for the element being added and the element being removed.

  Source Code

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

S = sum(A[:K])
ma = S
mi = S
for i in range(1, N - K + 1):
    S += A[i + K - 1] - A[i - 1]
    if S > ma:
        ma = S
    if S < mi:
        mi = S

print(ma - mi)

This editorial was generated by claude4.6opus-thinking.