Editorial for Maximum Window Sum

Approach

First compute the sum of the first window of length $k$. Then slide the window one position at a time:

• subtract the value leaving the window;
• add the value entering the window;
• update the best sum seen so far.

Each move changes the window sum in $O(1)$, so the full algorithm runs in $O(n)$ time.

Solution (Python)

n, k = map(int, input().split())
a = list(map(int, input().split()))

currSum = 0
for i in range(k):
    currSum += a[i]

ans = currSum
for i in range(k, n):
    currSum -= a[i - k]
    currSum += a[i]
    ans = max(ans, currSum)

print(ans)