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.

暴力解需要一個accumulative sum array，然後第一層for loop代表end pointer的位置，第二層for loop代表start pointer的位置，利用sums[i] - sums[j]就可以算出[j + 1, i]區間內的和，然後得到平均值比大小。

// Brute Force
double findMaxAverage(vector<int>& nums, int k) { // time: O(n^2); space: O(n)
    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;
}

但其實第一個做法的accumulative sum array可以用兩個變數sum和preSum替換掉。

// Space Optimized Brute Force
double findMaxAverage(vector<int>& nums, int k) { // time: O(n^2); space: O(1)
    double preSum = accumulate(nums.begin(), nums.begin() + k, 0);
    double sum = preSum, res = sum / 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;
}

利用binary search，先找到left和right兩個搜尋範圍的邊界，left先訂為整個nums array最小的數，right定為整個nums array裡最大的數，因為所求一定要介於這兩個左右邊界之間。假設所求的答案是maxAvg，那麼在合乎k限制的區間[i, j]內，j - i >= k，(nums[i] - maxAvg) + (nums[i + 1] - maxAvg) + ... + (nums[j - 1] - maxAvg) + (nums[j] - maxAvg) <= 0，因為maxAvg只是某個大小大於等於k的區間的平均值，所以並不是所有區間內的平均值都會這樣大，所以如果照上述的式子，應該會得到小於等於0結果。所以一但我們發現某個區間內的總和減掉我們當前想驗證的可能答案時，如果結果大於0，那麼說明還有其他更大的maxAvg，就把左邊界定為中間數再次進行binary search。

// Binary Search
double findMaxAverage(vector<int>& nums, int k) { // time: O(nlogn); space: O(n)
    int n = nums.size();
    vector<double> sums(n + 1, 0.0);
    double left = *min_element(nums.begin(), nums.end());
    double right = *max_element(nums.begin(), nums.end());
    while (left + 1e-5 < right) {
        double mid = left + (right - left) / 2.0, pre_min_sum = 0.0;
        bool mid_is_smaller = false;
        for (int i = 1; i <= n; ++i) {
            sums[i] = sums[i - 1] + (nums[i - 1] - mid);
            if (i >= k) { // the sum in [j, i] interval is larger than 0, which means there is another max avg
                pre_min_sum = min(pre_min_sum, sums[i - k]);
                if (sums[i] > pre_min_sum) {
                    mid_is_smaller = true;
                    break;
                }
            }
        }
        if (mid_is_smaller) left = mid;
        else right = mid;
    }
    return left;
}

優化空間使用，算accumulative sum可以只用兩個sum和preSum變數完成。

// Space Optimized Binary Search
double findMaxAverage(vector<int>& nums, int k) { // time: O(nlogn); space: O(1)
    double left = *min_element(nums.begin(), nums.end());
    double right = *max_element(nums.begin(), nums.end());
    while (left + 1e-5 < right) {
        double mid = left + (right - left) / 2.0, sum = 0.0, preSum = 0.0, preMinSum = 0.0;
        bool midIsSmaller = false;
        for (int i = 0; i < nums.size(); ++i) {
            sum += (nums[i] - mid);
            if (i >= k) {
                preSum += (nums[i - k] - mid);
                preMinSum = min(preMinSum, preSum);
            }
            if (i >= k - 1 && sum > preMinSum) {
                midIsSmaller = true;
                break;
            }
        }
        if (midIsSmaller) left = mid;
        else right = mid;
    }
    return left;
}

643. Maximum Average Subarray I