Maximum Average of a Fixed Window
Problem
Given an array nums and an integer k, return the largest average of any contiguous subarray of length exactly k. Slide a fixed-length window across the array and update the running sum in constant time per step.
Input
nums = [4, 1, 7, 3, 8, 2], k = 3Output
6.0Window [7, 3, 8] has sum 18, the largest among the four windows of length 3.
def 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 / kfunction maxAverage(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 maxAverage(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 maxAverage(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;
}