Overview

Given temperature data over \(N\) consecutive days, the problem asks to find the difference between the maximum and minimum values among all sums of \(K\) consecutive days.

Analysis

As a naive approach, if we individually compute the sum for every \(K\) consecutive days, there are \(N-K+1\) such sums, and each computation takes \(O(K)\) time, resulting in an overall time complexity of \(O(NK)\). Since \(N\) and \(K\) can be up to \(10^5\), the worst case would require \(10^{10}\) operations, which would not meet the time limit.

However, we notice that the sums of \(K\) consecutive days largely overlap between adjacent intervals. Specifically, the difference between \(S_i\) and \(S_{i+1}\) is simply that \(A_i\) is removed and \(A_{i+K}\) is added. By exploiting this property, we can compute the sum of the next interval in constant time.

Algorithm

1. Compute the sum of the first \(K\) days.
2. Set this sum as the initial values for both the maximum and minimum.
3. Slide the interval one day at a time, updating the sum:
   • Subtract the temperature of the first day of the current interval from the sum.
   • Add the temperature of the next day.
4. Use the updated sum to update the maximum and minimum values.
5. After processing all intervals, output the difference between the maximum and minimum.

This technique is called the “sliding window” and efficiently computes sums of consecutive subintervals.

Complexity

• Time complexity: \(O(N)\)
  • Computing the initial sum takes \(O(K)\), and the subsequent loop performs \(O(N-K)\) operations, so the overall complexity is \(O(N)\).
• Space complexity: \(O(N)\)
  • An array is needed to store the temperature data.

Implementation Notes

• After computing the sum of the first interval, the loop updates the sum using only subtraction and addition.

• The maximum and minimum are compared and updated at each step.

• For input reading, all data is read at once for efficiency.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    total = sum(A[:k])
    max_sum = total
    min_sum = total
    
    for i in range(1, n - k + 1):
        total = total - A[i-1] + A[i+k-1]
        if total > max_sum:
            max_sum = total
        if total < min_sum:
            min_sum = total
            
    print(max_sum - min_sum)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.