Overview

This is a problem where you examine the sum \(S_i\) for every contiguous subarray of length \(K\), and find the difference between the maximum and minimum values: \(\max(S_i) - \min(S_i)\).

Analysis

There are \(N-K+1\) sums of \(K\) consecutive days. If we naively compute each \(S_i\) as $\(S_i = A_i + A_{i+1} + \dots + A_{i+K-1}\)\( by summing \)K\( elements every time, the time complexity becomes \)O((N-K+1)K)\(. In the worst case, \)N\( and \)K\( are close to \)10^5\(, requiring around \)10^{10}$ additions, which will not fit within the time limit (TLE).

The key observation here is that the sums of adjacent intervals can be updated using “differences.”
For example: - \(S_1 = A_1 + A_2 + \dots + A_K\) - \(S_2 = A_2 + A_3 + \dots + A_{K+1}\)

So \(S_2\) is obtained by subtracting \(A_1\) from \(S_1\) and adding \(A_{K+1}\): $\(S_2 = S_1 - A_1 + A_{K+1}\)\( Similarly, in general: \)\(S_{i+1} = S_i - A_i + A_{i+K}\)\( This allows us to update each interval sum in \)O(1)\(, processing everything in \)O(N)$ overall. By tracking the minimum and maximum values during the updates, we simply output their difference at the end.

(Example) \(A=[1,3,2,5]\), \(K=2\)
- \(S_1=1+3=4\) - \(S_2=4-1+2=5\) - \(S_3=5-3+5=7\)
Maximum \(7\), minimum \(4\), difference is \(3\).

Algorithm

1. Compute the first interval sum \(S_1=\sum_{j=1}^{K} A_j\).
2. Initialize the minimum and maximum as \(mn=mx=S_1\).
3. For \(i=K, K+1, \dots, N-1\), update the current interval sum as follows: $\(window\_sum \leftarrow window\_sum + A_{i+1} - A_{i-K+1}\)$ (In a 0-indexed implementation: window_sum += A[i] - A[i-K])
4. After each update, update \(mn\) and \(mx\) with the new window_sum.
5. Finally, output \(mx-mn\).

This is the so-called sliding window (basic form of the two-pointer technique).

Complexity

• Time complexity: \(O(N)\) (each element is processed at most a constant number of times)
• Space complexity: \(O(N)\) (to store the array \(A\); this can be reduced to \(O(1)\) if the input is processed sequentially)

Implementation Notes

• After computing the initial interval sum, in the loop we update by “adding the incoming element and subtracting the outgoing element.”

• \(mn\) and \(mx\) must be initialized with the first interval sum; otherwise, missed updates can easily lead to WA.

• Since the input can be large, in Python it is advisable to use fast input methods such as sys.stdin.buffer.read() for stability.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    K = int(next(it))
    A = [int(next(it)) for _ in range(N)]

    window_sum = sum(A[:K])
    mn = mx = window_sum

    for i in range(K, N):
        window_sum += A[i] - A[i - K]
        if window_sum < mn:
            mn = window_sum
        if window_sum > mx:
            mx = window_sum

    print(mx - mn)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.