Sliding Window

Source

"""Sliding window pattern template.

Use for problems involving contiguous subarrays/substrings
where you need to find an optimal window satisfying some constraint.
"""

from collections.abc import Sequence
from typing import TypeVar

T = TypeVar("T")


def max_sum_subarray(nums: Sequence[int], k: int) -> int:
    """Return the maximum sum of any contiguous subarray of length k.

    Complexity:
        Time:  O(n)
        Space: O(1)

    >>> max_sum_subarray([2, 1, 5, 1, 3, 2], 3)
    9
    """
    if k <= 0 or k > len(nums):
        msg = f"k={k} out of range for length {len(nums)}"
        raise ValueError(msg)

    window_sum = sum(nums[:k])
    best = window_sum

    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # add incoming, drop the element k back
        best = max(best, window_sum)

    return best