Maximum Average Subarray I

Sliding Window

15 min

Problem Statement

You are given an integer array nums consisting of n elements, and an integer k. Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value.

Example

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4

nums: [1, 12, -5, -6, 50, 3], k: 4

Output: 12.75

Output: 12.75000

The subarray [12, -5, -6, 50] has the maximum average of (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75.

Solution

The problem can be solved using a fixed-size sliding window. We calculate the sum of the first `k` elements. Then, we slide the window one element at a time, updating the sum by subtracting the element that is leaving the window and adding the new element that is entering. We keep track of the maximum sum found so far.

Algorithm Steps

Calculate the sum of the first `k` elements.
Initialize `maxSum` with this initial sum.
Iterate from the `k`-th element to the end of the array.
Update the current sum by adding the current element and subtracting the element that is `k` positions behind.
Update `maxSum` with the maximum of `maxSum` and the current sum.
The result is `maxSum / k`.

Maximum Average Subarray

Fixed-Size Sliding Window

Progress1 / 1

Ready to start the visualization

nums

-5

-6

Current Sum

Max Sum

Maximum Average Subarray I Solution


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