Editorial for Maximum Window Sum

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

First compute the sum of the first window of length $k$ ~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)$ ~O(1)~, so the full algorithm runs in $O(n)$ ~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)

Comments

There are no comments at the moment.