Maximum Average Subarray I
Easy· fixed window
Problem
Find the contiguous subarray of exactly length k with the largest average, and return that average.
Examples
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75
The window [12,-5,-6,50] sums to 51, and 51 / 4 = 12.75.
Input: nums = [5], k = 1
Output: 5.0
Constraints
- • 1 <= k <= nums.length <= 10^5
- • -10^4 <= nums[i] <= 10^4
Hints & approach
Hint 1
Maximising the average of a fixed-size window is the same as maximising its sum.
Hint 2
When the window slides by one, only two elements change.
Approachtry the hints first
Sum the first k elements. Then slide the window one step at a time: add the element entering on the right and subtract the one leaving on the left, updating the best sum. Divide the best sum by k at the end. Each element enters and leaves once.
Time O(n) · Space O(1)