Maximum Average Subarray I

Share

Given an integer array nums and integer k, find a contiguous subarray of length k that has the maximum average. Return this maximum average.

Example 1
Input: nums=[1,12,-5,-6,50,3], k=4 → Output: 12.75
Example 2
Input: nums=[5], k=1 → Output: 5.0

Solution Approach

Use a fixed-size sliding window of size k. Compute the initial sum of first k elements, then slide the window by subtracting the leftmost element and adding the new rightmost element.

  • Compute sum of first k elements.
  • Slide from index k to n-1: add nums[i], subtract nums[i-k].
  • Track maximum sum throughout.
  • Return maxSum / k as double.
Java
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) sum += nums[i];
        int maxSum = sum;
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - nums[i - k];
            maxSum = Math.max(maxSum, sum);
        }
        return (double) maxSum / k;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(1)