Maximum Average Subarray I

Intuition

Every candidate block has the same length k, so comparing averages is the same as comparing their sums. Rather than recomputing each window's sum from scratch, we compute the first window once and then slide: each shift adds the incoming element on the right and drops the outgoing element on the left. That keeps every update constant time, so a single left-to-right pass reveals the largest window sum. Dividing that best sum by k at the end converts it to the maximum average.

Algorithm walkthrough

1. 1Add the first k elements to form the initial window sum and treat it as the current best.
2. 2Slide the window right by one: add nums[i] and subtract nums[i - k].
3. 3After each slide, update the best sum if the new window sum is larger.
4. 4Continue until the window reaches the end of the array.
5. 5Divide the best sum by k and return it as a floating-point average.

Implementation

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        window_sum = sum(nums[:k])
        best = window_sum
        for i in range(k, len(nums)):
            window_sum += nums[i] - nums[i - k]
            best = max(best, window_sum)
        return best / k