Overview

A problem to find the difference between the maximum and minimum values among the sums of temperatures over every consecutive \(K\)-day period.

Analysis

In this problem, we need to calculate the sum of temperatures for all consecutive \(K\)-day periods, and find the difference between the maximum and minimum among those sums.

A naive approach would be to directly compute \(S_i = A_i + A_{i+1} + \dots + A_{i+K-1}\) for each starting position \(i\), resulting in a time complexity of \(O(N \cdot K)\). However, since the constraints allow \(N\) and \(K\) to be up to \(10^5\), this approach would require up to approximately \(10^{10}\) operations in total, which cannot be completed within the time limit (roughly a few seconds) and would result in TLE.

An efficient alternative is the “sliding window” technique. This method quickly computes the next interval sum by swapping out one element at each end from the previous interval sum.

For example, consider the following input:

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

Suppose we already know the first interval sum \(S_1 = 1 + 2 + 3 = 6\). To compute the next sum \(S_2 = 2 + 3 + 4\) by shifting the interval one position to the right, we simply subtract the leftmost element \(1\) and add the new rightmost element \(4\):

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

By updating using differences in this way, each interval sum can be computed in \(O(1)\), reducing the overall time complexity to \(O(N)\).

Using this method, we can maintain and update the maximum and minimum of all interval sums as we go, and output their difference at the end to obtain the answer.

Algorithm

1. Compute the sum of the first \(K\) terms \(S_1\) and store it as current_sum.
2. Initialize max_sum and min_sum with current_sum.
3. For each subsequent interval, update the sum using the difference:
   • current_sum = current_sum - A[i - 1] + A[i + K - 1]
4. Update max_sum and min_sum with the updated current_sum.
5. Finally, output max_sum - min_sum.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding input)

Implementation Notes

• Update the interval sum using differences; avoid recalculating the sum of \(K\) elements each time.

• After computing the initial sum, be careful to avoid index errors in the loop (range(1, N - K + 1)).

• Update the maximum and minimum values at every step to ensure no comparisons are missed.

  Source Code

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()

This editorial was generated by qwen3-coder-480b.