Max Average Subarray
Description
Given an integer array nums and an integer k, find a contiguous subarray whose length is equal to k that has the maximum average value. Return this maximum average.
Example 1:
Input: nums = [1, 12, -5, -6, 50, 3], k = 4
Output: 12.75
Explanation: Maximum average is (12 + -5 + -6 + 50) / 4 = 51 / 4 = 12.75
Example 2:
Input: nums = [5], k = 1
Output: 5.0
Explanation: Only one element, so average is 5.0
Example 3:
Input: nums = [0, 4, 0, 3, 2], k = 1
Output: 4.0
Explanation: When k=1, we just find the maximum element = 4.
Constraints
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Complexity
Show Complexity
- Time:
O(n) - Space:
O(1)
Hints
Show Hints
- Pattern
- Use a fixed-size sliding window of size k
- Approach
- Same as max sum subarray - find max sum of size k, then return max_sum / k
- Complexity
- Track max sum, divide by k only at the end for average
Solutions
Show PY Solution
def solution(nums, k):
if k == 0:
return 0.0
curr = 0.0
for i in range(k):
curr += nums[i]
ans = curr / k
for i in range(k, len(nums)):
curr += nums[i] - nums[i - k]
ans = max(ans, curr / k)
return ans