644. Maximum Average Subarray II

Description

Given an array consisting ofnintegers, find the contiguous subarray whoselength is greater than or equal tokthat 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.

Discussion

Method

Binary Search.

Range from smallest to largest.Mid is the average value(can be viewed as the average of any length of subarray)

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int min = INT_MAX;
        int max = INT_MIN;

        for(auto num : nums) {
            min = std::min(num, min);
            max = std::max(num, max);
        }

        double start = min;
        double end = max;
        double mid = start + (end - start) / 2;
        while(end - start > 0.0000001) {
            mid = start + (end - start) / 2;
            if(true == check(nums, k, mid)) {
                start = mid;
            }
            else {
                end = mid;
            }
        }

        return mid;
    }
private:
    bool check(vector<int> &nums, int k, double avg) {
        vector<double> doubleNums(nums.size(), 0);
        for(int i = 0; i < nums.size(); ++i) {
            doubleNums[i] = nums[i] - avg;
        }

        double curAvg = 0;
        double preAvg = 0;
        for(int i = 0; i < nums.size();++i) {
            curAvg += doubleNums[i];

            if(i >= k) {
                preAvg += doubleNums[i - k];
            }

            if(preAvg < 0) {
                curAvg -= preAvg;
                preAvg = 0;
            }

            if(i >= k - 1  && curAvg >= 0) {
                return true;
            }
        }

        return false;
    }
};