Maximum Average Subarray I
You're given an integer array nums and an integer k, where k is at most the length of nums. Among all contiguous subarrays of exactly k elements, find the one with the largest average, and return that average as a floating-point number. Answers within 10^-5 of the true value are accepted.
Examples
nums = [1,12,-5,-6,50,3], k = 4 returns 12.75000
The three windows of length 4 sum to 2, 51, and 42. The best is [12,-5,-6,50], and 51 / 4 = 12.75.
nums = [5], k = 1 returns 5.00000
The only window is [5], so the answer is 5.
Constraints
- 1 <= k <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Hints
All the windows are the same length. What does that tell you about comparing averages?
Use a fixed-size sliding window and keep a running sum.
Sum nums[0..k-1] and set best to it. For i from k to n - 1, add nums[i], subtract nums[i - k], and update best. Return best / k.
Drill This: Your Approach First
Approach
Every window has the same length k, so the largest average belongs to the window with the largest sum: compare sums and divide once at the end. Add up the first k values, then slide the window one step at a time by adding the value that enters on the right and subtracting the one that leaves on the left, nums[i - k]. Each step costs O(1), where recomputing every window from scratch would cost O(n * k).
Time
O(n)
Space
O(1)
Pitfall
Solutions
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];
best = Math.max(best, sum);
}
return (double) best / k;
}
}class Solution:
def findMaxAverage(self, nums, k: int) -> float:
total = sum(nums[:k])
best = total
for i in range(k, len(nums)):
total += nums[i] - nums[i - k]
best = max(best, total)
return best / k