Overview

Given an array \(A\) of length \(N\), the problem asks to find a contiguous subarray of \(K\) elements with the maximum sum, and output that maximum value.

Analysis

When selecting \(K\) consecutive trees, the harvest is the sum of that interval \(\sum A_i\). Therefore, we need to find the “maximum sum of a contiguous subsequence of length \(K\).”

A naive approach would be, for every starting position \(l\) (\(1 \le l \le N-K+1\)): - Compute the sum of the interval \([l, l+K-1]\) by adding \(K\) elements each time

This results in a complexity of \((N-K+1)\times K\), which is \(O(NK)\) in the worst case. Given the constraint \(N \le 2\times 10^5\), for example when \(N=K=2\times 10^5\), this would require about \(4\times 10^{10}\) additions, which will not finish in time (TLE).

The key observation here is that the sum of adjacent intervals can be computed with only a small update. For example, when shifting the interval one position to the right:

• Previous interval: \(A_l + A_{l+1} + \cdots + A_{l+K-1}\)
• Next interval: \(A_{l+1} + A_{l+2} + \cdots + A_{l+K}\)

So the next interval’s sum can be updated by simply “subtracting \(A_l\) from the previous sum and adding \(A_{l+K}\).”

Example: \(A=[3,1,4,1,5]\), \(K=3\) The first sum is \(3+1+4=8\). The next interval is \(8 - 3 + 1 = 6\) (\(1+4+1\)), computed in \(O(1)\).

Using this approach (sliding window), the entire problem can be processed in \(O(N)\).

Algorithm

We use a sliding window (updating the sum of a fixed-length interval).

1. Compute the sum of the first \(K\) elements \(window\_sum = \sum_{i=1}^{K} A_i\), and set this as the tentative maximum \(best\).
2. For \(i=K\) to \(N-1\) (0-indexed), shift the interval one position to the right by updating:
   • \(window\_sum \leftarrow window\_sum + A[i] - A[i-K]\) (add the new right end and subtract the old left end).
3. After each update, take \(best = \max(best, window\_sum)\).
4. Finally, output \(best\).

Complexity

• Time complexity: \(O(N)\) (each element is processed at most a constant number of times)
• Space complexity: \(O(1)\) (constant space excluding the input array; storing array \(A\) itself requires \(O(N)\))

Implementation Notes

• Since \(A_i\) can be up to \(10^9\) and \(K\) can be up to \(2\times 10^5\), the sum can reach approximately \(2\times 10^{14}\). Python’s int supports arbitrary precision, so this is safe as-is.

• Writing the loop as for i in range(K, N): with the update formula window_sum += A[i] - A[i - K] helps reduce mistakes.

• Since the input can be large, using sys.stdin.buffer.readline ensures stable and fast input reading.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    window_sum = sum(A[:K])
    best = window_sum
    for i in range(K, N):
        window_sum += A[i] - A[i - K]
        if window_sum > best:
            best = window_sum
    print(best)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.