Maximum Average Subarray I

easy array sliding window

Problem

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Inputnums = [4, 1, 7, 3, 8, 2], k = 3

Output6.0

Window [7, 3, 8] has sum 18, the largest among the four windows of length 3.

nums (comma-separated)

def find_max_average(nums, k):
    s = sum(nums[:k])
    best = s
    for i in range(k, len(nums)):
        s += nums[i] - nums[i - k]
        if s > best:
            best = s
    return best / k

function findMaxAverage(nums, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k];
    if (sum > best) best = sum;
  }
  return best / k;
}

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) sum += nums[i];
        int best = sum;
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - nums[i - k];
            if (sum > best) best = sum;
        }
        return (double) best / k;
    }
}

double findMaxAverage(vector<int>& nums, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += nums[i];
    int best = sum;
    for (int i = k; i < (int)nums.size(); i++) {
        sum += nums[i] - nums[i - k];
        if (sum > best) best = sum;
    }
    return (double)best / k;
}

Explanation

Since every candidate window has the same fixed length k, the one with the biggest average is just the one with the biggest sum. So we only need to track sums and divide by k at the very end.

We compute the sum of the first k elements once. Then we slide the window one step at a time: add the new element entering on the right and subtract the one leaving on the left. That keeps the sum current in a single operation.

We remember the largest sum seen in best, and finally return best / k as the maximum average.

Example: nums = [4,1,7,3,8,2], k = 3. The first window [4,1,7] sums to 12. Sliding gives [1,7,3]=11, [7,3,8]=18, [3,8,2]=13. The max sum 18 divided by 3 is 6.0.

Because each slide is one add and one subtract, the whole scan is linear time with constant extra space.

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