Maximum Average Subarray

643.Maximum Average Subarray I

Array

Sliding Window

Problem Statement:

Find a contiguous subarray of length k within the array nums that has the maximum average value. Return the maximum average value.

Example:

Input:

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

→

Output:

12.75

Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Algorithm:

1. Use sliding window technique to track sum of k elements
2. Add incoming element to sum
3. Subtract outgoing element (i-k) when window exceeds k size
4. Update maximum sum when window size is k
5. Return maximum sum divided by k

Complexity:

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

Java Solution:

public double findMaxAverage(int[] nums, int k) {
    int sum = 0;
    int max = Integer.MIN_VALUE;

    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];                           // Add current element
        
        if (i - k >= 0)                       // Remove element outside window
            sum -= nums[i - k]; 
            
        if (i - k >= -1)                      // Update max when window size is k
            max = Math.max(sum, max);
    }

    return (double) max/k;
}

Python Solution:

def findMaxAverage(self, nums: List[int], k: int) -> float:
    curr_sum = 0
    max_sum = float('-inf')
    
    for i in range(len(nums)):
        curr_sum += nums[i]                  # Add current element
        
        if i >= k:                         # Remove element outside window
            curr_sum -= nums[i - k]
            
        if i >= k - 1:                    # Update max when window size is k
            max_sum = max(max_sum, curr_sum)
    
    return max_sum / k

C++ Solution:

double findMaxAverage(vector<int>& nums, int k) {
    int sum = 0;
    int max_sum = INT_MIN;
    
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];                      // Add current element
        
        if (i >= k)                         // Remove element outside window
            sum -= nums[i - k];
            
        if (i >= k - 1)                    // Update max when window size is k
            max_sum = max(max_sum, sum);
    }
    
    return (double)max_sum / k;
}