Given an array with positive and negative numbers, find themaximum average subarraywhich length should be greater or equal to given lengthk.

Notice

It's guaranteed that the size of the array is greater or equal tok.

Have you met this question in a real interview?

Yes

Example

Given nums =[1, 12, -5, -6, 50, 3], k =3

Return15.667// (-6 + 50 + 3) / 3 = 15.667

class Solution {

public:

/
**

* @param nums an array with positive and negative numbers

* @param k an integer

* @return the maximum average

*/

double maxAverage(vector<int>& nums, int k) {

        // Write your code here

        double l = INT_MAX, r = INT_MIN;

        for (int i = 0; i < nums.size(); ++i) {

        if (nums[i] < l) {

            l = nums[i];

        }

        if (nums[i] > r) {

            r = nums[i];

        }

    }

    while (r - l >= 1e-6) {

        double m = (r + l) / 2;

        if (CheckAverage(nums, k, m))

            l = m;

        else

            r = m;

    }

    return l;

}



bool CheckAverage(vector<int>& nums, int k, double val) {

    vector<double> sums(nums.size() + 1, 0);

    double min_pre = 0;

    for (int i = 1; i <= nums.size(); ++i) {

        sums[i] = sums[i - 1] + nums[i - 1] - val;

        if (i >= k) {

        min_pre = min(min_pre, sums[i - k]);

    }

    if (i >= k && sums[i] >= min_pre) {

        return true;

    }

}



return false;

}

};