Maximum Average Subarray I

Problem:
https://leetcode.com/problems/maximum-average-subarray-i/description/

Given an array nums and an integer k, find the maximum average value of any contiguous subarray of length k.

This is a classic sliding window problem.

💡 Approach

Instead of recomputing the sum of every subarray (which would be O(n·k)), we use a sliding window:

1. Compute the sum of the first k elements.
2. Slide the window one element at a time:
   • Subtract the element leaving the window
   • Add the element entering the window
3. Track the maximum sum seen.
4. Divide by k to get the maximum average.

Why this works

Each window update takes O(1) time, so the total runtime is O(n).

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

def findMaxAverage(nums, k):
    # sum of first k elements
    max_sum = sum(nums[:k])

    # sliding window pointers
    l = 0
    r = k
    curr_sum = max_sum

    while r < len(nums):
        # slide window: remove left, add right
        curr_sum = curr_sum + nums[r] - nums[l]

        if curr_sum > max_sum:
            max_sum = curr_sum

        l += 1
        r += 1

    # convert to float for correct division
    k = float(k)
    max_sum = float(max_sum)
    return max_sum / k


# example test
print(findMaxAverage([1, 12, -5, -6, 50, 3], 4))