Formatted question description: https://leetcode.ca/all/644.html

# 644. Maximum Average Subarray II

Hard

## Description

Given an array consisting of n integers, find the contiguous subarray whose length is greater than or equal to k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4

Output: 12.75

Explanation:

When length is 5, maximum average value is 10.8,

When length is 6, maximum average value is 9.16667.

Thus return 12.75.

Note:

1. 1 <= k <= n <= 10,000.
2. Elements of the given array will be in range [-10,000, 10,000].
3. The answer with the calculation error less than 10-5 will be accepted.

## Solution

Use binary search. Initialize min and max to be the minimum element in nums and the maximum element in nums, respectively. Each time calculate mid as the average of min and max, and maintain prevMid which stores the previous value of mid. After mid is calculated, check whether there exists a subarray of nums such that its average value is at least mid. If so, set min = mid. Otherwise, set max = mid. Then calculate the error as the absolute difference between mid and prevMid and set prevMid = mid. The binary search ends when the error does not exceed 10^-5. Finally, return min.

• class Solution {
public double findMaxAverage(int[] nums, int k) {
final double EPSILON = 0.00001;
double min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
double prevMid = max;
double error = Integer.MAX_VALUE;
while (error > EPSILON) {
double mid = (min + max) / 2;
if (exist(nums, mid, k))
min = mid;
else
max = mid;
error = Math.abs(mid - prevMid);
prevMid = mid;
}
return min;
}

public boolean exist(int[] nums, double mid, int k) {
double sum = 0, prefixSum = 0, minSum = 0;
for (int i = 0; i < k; i++)
sum += nums[i] - mid;
if (sum >= 0)
return true;
int length = nums.length;
for (int i = k; i < length; i++) {
sum += nums[i] - mid;
prefixSum += nums[i - k] - mid;
minSum = Math.min(minSum, prefixSum);
if (sum >= minSum)
return true;
}
return false;
}
}

• Todo

• class Solution(object):
# just guess the answer by binary search
# note that we can check if there is a subarray that has avg. sum >= a certain value in linear time
# then overall time complexity is O(nlog(max(nums) - min(nums)))
def _findMaxAverage(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: float
"""

def valid(nums, mid, k):
minSum = preSums = sums = 0
for i in range(k):
sums += nums[i] - mid
if sums >= 0:
return True
for i in range(k, len(nums)):
sums += nums[i] - mid
preSums += nums[i - k] - mid
minSum = min(minSum, preSums)
if sums - minSum >= 0:
return True
return False

lo = min(nums)
hi = max(nums)
while hi - lo > 1e-5:
mid = (hi + lo) / 2.
if valid(nums, mid, k):
lo = mid
else:
hi = mid
return lo

# have to use this hack to pass OJ
def findMaxAverage(self, nums, k):
import numpy as np
lo, hi = min(nums), max(nums)
nums = np.array([0] + nums)
while hi - lo > 1e-5:
mid = nums[0] = (lo + hi) / 2.
sums = (nums - mid).cumsum()
mins = np.minimum.accumulate(sums)
if (sums[k:] - mins[:-k]).max() > 0:
lo = mid
else:
hi = mid
return lo