# 644. Maximum Average Subarray II

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.

``````class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int n = nums.size();
vector<int> sums = nums;
for (int i = 1; i < n; ++i) {
sums[i] = sums[i - 1] + nums[i];
}
double res = (double)sums[k - 1] / k;
for (int i = k; i < n; ++i) {
double t = sums[i];
if (t > res * (i + 1)) res = t / (i + 1);
for (int j = i - k; j >= 0; --j) {
t = sums[i] -  sums[j];
if (t > res * (i - j)) res = t / (i - j);
}
}
return res;
}
};
``````

``````class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double preSum = accumulate(nums.begin(), nums.begin() + k, 0);
double sum = preSum, res = preSum / k;
for (int i = k; i < nums.size(); ++i) {
preSum += nums[i];
sum = preSum;
if (sum > res * (i + 1)) res = sum / (i + 1);
for (int j = 0; j <= i - k; ++j) {
sum -= nums[j];
if (sum > res * (i - j)) res = sum / (i - j);
}
}
return res;
}
};
``````

[1, 2, 3, 4]   k = 2

``````class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int n = nums.size();
vector<double> sums(n + 1, 0);
double left = *min_element(nums.begin(), nums.end());
double right = *max_element(nums.begin(), nums.end());
while (right - left > 1e-5) {
double minSum = 0, mid = left + (right - left) / 2;
bool check = false;
for (int i = 1; i <= n; ++i) {
sums[i] = sums[i - 1] + nums[i - 1] - mid;
if (i >= k) {
minSum = min(minSum, sums[i - k]);
}
if (i >= k && sums[i] > minSum) {check = true; break;}
}
if (check) left = mid;
else right = mid;
}
return left;
}
};
``````

``````class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double left = *min_element(nums.begin(), nums.end());
double right = *max_element(nums.begin(), nums.end());
while (right - left > 1e-5) {
double minSum = 0, sum = 0, preSum = 0, mid = left + (right - left) / 2;
bool check = false;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i] - mid;
if (i >= k) {
preSum += nums[i - k] - mid;
minSum = min(minSum, preSum);
}
if (i >= k - 1 && sum > minSum) {check = true; break;}
}
if (check) left = mid;
else right = mid;
}
return left;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/644

Maximum Average Subarray I

https://leetcode.com/problems/maximum-average-subarray-ii/

https://leetcode.com/problems/maximum-average-subarray-ii/discuss/105498/c-binary-search-130ms

https://leetcode.com/problems/maximum-average-subarray-ii/discuss/105495/10-line-c-ac-barely-solution-on2

https://leetcode.com/problems/maximum-average-subarray-ii/discuss/105484/C%2B%2B-solution-simple-improvement-to-brute-force-O(nk)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation