To solve the problem of finding the maximum average of a contiguous subarray with at least k elements, we use a binary search approach. This method efficiently narrows down the possible average values by checking if a candidate average can be achieved with a subarray of length at least k.
Approach
- Binary Search on Average: The possible range of the average is between the minimum and maximum values in the array. We perform binary search on this range.
- Check Feasibility: For each candidate average
mid, we transform the array into a new array where each element isarr[i] - mid. We then check if there exists a subarray of length at leastkwith a non-negative sum (since this implies the average of the subarray is at leastmid). - Efficient Check: To check feasibility, we use prefix sums and track the minimum prefix sum up to
i - kfor each positioni. This allows us to determine if any valid subarray exists in linear time.
Solution Code
def check(arr, k, mid):
n = len(arr)
prefix_sum = [0.0] * (n + 1)
for i in range(n):
prefix_sum[i + 1] = prefix_sum[i] + arr[i] - mid
min_prefix = prefix_sum[0] # Minimum prefix sum up to index 0
for i in range(k, n + 1):
# Check if there exists a subarray ending at i-1 with length >=k
if prefix_sum[i] - min_prefix >= 0:
return True
# Update min_prefix to include the next possible prefix sum for future checks
min_prefix = min(min_prefix, prefix_sum[i - k + 1])
return False
def findMaxAverage(arr, k):
low = min(arr)
high = max(arr)
# Perform binary search for sufficient precision (100 iterations)
for _ in range(100):
mid = (low + high) / 2
if check(arr, k, mid):
low = mid
else:
high = mid
return low
Explanation
- Binary Search: The binary search runs for 100 iterations to ensure high precision (since each iteration halves the interval, 100 iterations give a precision of about
1e-30). - Feasibility Check:
- Prefix Sum: We compute the prefix sum of the transformed array (
arr[i] - mid). This helps in quickly calculating the sum of any subarray. - Minimum Prefix: For each position
i(starting fromk), we check if the current prefix sum minus the minimum prefix sum up toi - kis non-negative. This ensures we find the best possible subarray ending ati-1with length at leastk.
- Prefix Sum: We compute the prefix sum of the transformed array (
This approach efficiently handles large arrays (up to 1e5 elements) with a time complexity of O(n log(max(arr) - min(arr))), which is optimal for this problem. The space complexity is O(n) for the prefix sum array, but it can be optimized to O(1) if we track the prefix sum and minimum prefix on the fly.
Example: For the array [1,12,-5,-6,50,3] and k=4, the maximum average is 12.75 (from the subarray [12,-5,-6,50]). The code correctly identifies this by checking the candidate average 12.75 and returning True for feasibility.
This solution is robust and works for all edge cases, including when k equals the length of the array or k=1. It provides the required precision for floating-point averages.


作者声明:本文包含人工智能生成内容。