644. Maximum Average Subarray II

Problem:

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.

Analysis:

6/20/2018 update:
Use binary search to guess the average value. And make sure the error is within 0.00001.

To compare the average, for instance, a1, a2, a3, a4 and b1, b2, b3, b4. If (a1-b1) + (a2-b2)

 + (a3-b3) + (a4-b4) > 0, we can tell that a's average is greater than b.

preSum is the sum that k away from current index(subaray length greater than or equal to k). Comparing current sum and minimum preSum, we can tell whether the picked mid is smaller or greater. 

Solution:

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;    
        
        for (int n: nums) {
            min = Math.min(min, n);
            max = Math.max(max, n);
        }
        
        double error = Integer.MAX_VALUE;
        double preMid = max;
        while (error > 0.00001) {
            double mid =  (max + min) * 0.5;
            if (isGreaterThanMid(nums, k, mid)) {
                min = mid;
            } else {
                max = mid;
            }
            error = Math.abs(preMid - mid);
            preMid = mid;
        }
        return min;
    }

    private boolean isGreaterThanMid(int[] nums, int k, double mid) {
        double sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i] - mid;
        }
        if (sum >= 0)
            return true;
        double preSum = 0, min = 0;
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - mid;
            preSum += nums[i - k] - mid;
            min = Math.min(preSum, min);
            if (sum >= min)
                return true;
        }
        return false;
    }
}

--------------------------------------------------------------------------------------------------------------------------
思路：
发现了一个小规律，有些难题是几个知识点的结合，比如这道题。还有一道难题word ladder II,是DFS和BFS结合。

Maximum Average Subarray I思路很简单，因为窗口是固定的k。从前往后移，更新max average。这道题可以用类似的方法，时间复杂度是O(n2)。

另外一种方法是采用二分法，时间复杂度O(nlogn)。见leetcode article https://leetcode.com/problems/maximum-average-subarray-ii/solution/



实现：
在更新minSum的时候可以另外开一个变量prevSum，从而避免了使用sum[] 数组，节省了空间。