lintcode617. Maximum Average Subarray II

Intuition

Find maximum average subarray which length should be greater or equal to given length k.

  • the minimum average is the minimum of array, the maximum average is the maximum of array.

  • binary search mid between minimum and maximum, if sum(subarray) - mid * len(subarray) > 0, then minimum = mid

  • how to judge it in binary search?

    • use pre-sum array sum[] denotes sum(nums[0] - mid, ..., nums[i] - mid)

    • mn denotes the minimum sum from 0 to i - k

    • if i >= k && sum[i] > mn, prove that there is sum(nums[j] - mid, ..., num[i] - mid) > 0, the real average will greater than mid.

Solution

class Solution {
public:
/**
* @param nums: an array with positive and negative numbers
* @param k: an integer
* @return: the maximum average
*/
bool judge(vector<int>& nums, double res, int k)
{
int n = nums.size();
vector<double> sum(n + 1);
double mn = 0;
for (int i = 1; i <= n; i++)
{
sum[i] = sum[i - 1] + (double)nums[i - 1] - res;
if (i >= k && sum[i] > mn)
return true;
if (i >= k)
mn = min(mn, sum[i + 1 - k]);
}
return false;
}
​
double maxAverage(vector<int> &nums, int k) {
if (nums.empty()) return 0.0;
int n = nums.size();
double mn = nums[0], mx = nums[0];
for (int i = 1; i < n; i++)
{
mn = min(mn, (double)nums[i]);
mx = max(mx, (double)nums[i]);
}
​
double res = mx;
while (mx - mn > 1e-8)
{
res = (mx + mn) / 2.0;
if (judge(nums, res, k))
mn = res;
else
mx = res;
}
return res;
}
};