leetcode 644 - Maximum Average Subarray II

https://leetcode.com/problems/maximum-average-subarray-ii/
https://leetcode.com/problems/maximum-average-subarray-ii/discuss/105479/C%2B%2B-Binary-Search-O(nlogn)

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 <= k <= n <= 10,000.
Elements of the given array will be in range [-10,000, 10,000].
The answer with the calculation error less than 10-5 will be accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double left = INT_MAX, right = INT_MIN;

for (int n : nums) {
left = min(left, static_cast<double>(n));
right = max(right, static_cast<double>(n));
}

while (right - left > 10e-6) {
double mid = left + (right - left) / 2;

if (check(nums, k, mid))
left = mid;
else
right = mid;
}

return left + (right - left) / 2;
}

/*
(a1 + a2 + ... + aj) / j >= mid
a1 + a2 + ... + aj >= j * mid
a1 + a2 + ... + aj - j * mid >= 0
(a1 - mid) + (a2 - mid) + ... + (aj - mid) >= 0
*/
bool check(vector<int>& nums, int k, double mid) {
int size = nums.size();
vector<double> prefix_sum(size + 1);

prefix_sum[0] = 0.0;
for (int i = 1; i <= size; i++)
prefix_sum[i] = prefix_sum[i-1] + static_cast<double>(nums[i-1]) - mid;

double pre_min = 0.0;
for (int i = k; i <= size; i++) {
if (prefix_sum[i] > pre_min) return true;
pre_min = min(pre_min, prefix_sum[i-k+1]);
}

return false;
}
};