643. Maximum Average Subarray I Easy

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. Any answer with a calculation error less than 10^-5 will be accepted.

Example 1: Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2: Input: nums = [5], k = 1
Output: 5.00000

Approach

Input: Given an array

Output: Find the maximum average, requiring it to be a contiguous subarray of length k

This problem falls under the Fixed-length Sliding Window category.

We can use a sliding window of size k, maintaining the total sum of the current window as we traverse the array, and calculate its average. Every time the window slides to the right, we simply subtract the value of the element shifting out from the left and add the value of the new element entering from the right, which allows us to update the window sum in O(1) time.

Meanwhile, use a variable to keep track of the maximum average seen so far. Upon finishing the traversal, we'll obtain the final answer.

Implementation

python

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        window_sum = 0  # Initialize the sum of elements inside the sliding window

        # Calculate the total sum of the first window of length k
        for i in range(0, k):
            window_sum += nums[i]
        
        # Initialize the maximum average
        max_value = window_sum / k

        # Starting from the k-th element, slide the window
        for i in range(k, len(nums)):
            # Remove an element from the left of the window (nums[i - k]) and add a new element to the right (nums[i])
            diff = nums[i] - nums[i - k]
            window_sum += diff  # Update window sum

            # Calculate the average of the current window and update the max value
            max_value = max(max_value, window_sum / k)
        
        return max_value  # Return the maximum average

javascript

const findMaxAverage = function (nums, k) {
    let windowSum = 0;

    // First calculate the total sum of the first window (first k numbers)
    for (let i = 0; i < k; i++) {
        windowSum += nums[i];
    }

    // The initial maximum average is just the average of the first window
    let maxValue = windowSum / k;

    // Slide the window, traversing forwards starting from the k-th element
    for (let i = k; i < nums.length; i++) {
        // Current window = Previous window + Newly entering element - Element sliding out
        const diff = nums[i] - nums[i - k];

        // Update the sum representing current window bounds
        windowSum += diff;

        // Keep updating the recorded highest potential average 
        maxValue = Math.max(maxValue, windowSum / k);
    }

    // Forward the best determined average
    return maxValue;
}

Complexity Analysis

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

Links

643. Maximum Average Subarray I (English)643. 子数组最大平均数 I (Chinese)