Fixed-Size Window

Fixed window of size $k$ slides across array, updating a running value.

Max sum of $k$ elements:

function maxSumSubarray(arr, k):
    windowSum = sum of arr[0..k-1]
    maxSum = windowSum
    for i from k to n-1:
        windowSum = windowSum + arr[i] - arr[i-k]
        maxSum = max(maxSum, windowSum)
    return maxSum

Add entering element, remove leaving. $O(1)$ update.

Time: $O(n)$. Space: $O(1)$.