Easy Sliding Window Arrays & Strings
In plain English: Find which group of k consecutive elements in an array has the biggest total.
Instead of recalculating the sum from scratch, subtract the leaving element and add the entering one — O(1) per slide.
Prompt
Given array a and window size k, find the maximum sum of any contiguous k elements.
Try to write it from scratch before scrolling down.
Solution
def max_sum_k(a, k):
window = sum(a[:k])
best = window
for i in range(k, len(a)):
window += a[i] - a[i - k] # slide: add right, drop left
best = max(best, window)
return best
# Test: max_sum_k([1,4,2,10,2,3,1,0,20], 4) == 24