LeetCode 643/644 - Maximum Average Subarray I/II

https://leetcode.com/problems/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.

X. Bisection
https://www.jianshu.com/p/f37ec579dd11

(nums[i]+nums[i+1]+…+nums[j])/(j-i+1)>x
=>nums[i]+nums[i+1]+…+nums[j]>x*(j-i+1)
=>(nums[i]-x)+(nums[i+1]-x)+…+(nums[j]-x)>0
于是我们从结果x里面去找，x用binary search.
然后再用sliding window表示范围内的sum

https://blog.csdn.net/magicbean2/article/details/79142613
我们首先找出数组中的最小值left和最大值right，因为这将构成最大平均值的区间。然后每次找到left和right的平均值mid，对于mid，在数组内找是否存在一个长度大于等于k的连续区间，其平均值大于mid，如果存在，那么说明mid还不是最大平均值，所以修改左边界left；否则说明mid已经大于等于左右长度大于等于k的所有连续区间的最大平均值了，所以此时修改右边界right。这样当left和right逐渐收敛到一点的时候，该收敛点就是最大平均值。

该算法的空间复杂度是O(1)，时间复杂度是O(logm*n)，其中n是nums的长度，而m则是nums中最大值和最小值的差。虽然m有可能很大，但是被log了，所以该时间复杂度接近于O(n)，还是非常不错的。
https://blog.csdn.net/MebiuW/article/details/76222743
这道题的思想就是二分猜测，首先需要预测的这个平均值肯定是介于最大值和最小值之间的，所以就以二分法的思想，不停的猜测就可以了，这个就是核心思想，进行二分法的需要操作log(max-min)次。

我们不停的猜测那个mid值（max和min的平均值）在给定的序列中能否满足，也就是说是否存在一个大于等于k的区间的平均值大于等于mid值，如果是，我们就可以把下限值min变成mid，反之改变max，就这样做，直到猜测范围小于0.00001就可以直接给出答案了（题目说了有误差的容许范围，小提示吧）。

另外一个难点在于如何在线性的时间内，判别nums当中是否存在这样的一段，使得平均值大于等于mid。做法也很简单：
顺序遍历数组nums（这里需要统一减去mid），统计两个值这里第一个值是sums，从位置0到当前位置j的和。另外一个是从0到某个位置i的和的最小值min_sum（其中i小于j，且i和j的长度大于等于k）。也就是等价于找一段和大于0的子区间，注意不是找最大，所以不用太严格。。
http://xuezha.blogspot.com/2017/09/leetcode-644maximum-average-subarray-ii.html

1. 只要满足一定误差，所以用二分，直接二分最后的平均值

2. 在判断某个平均值是否满足时，转换为求连续子数组的和大于0（这个求平均值的套路可以记一下）

城市套路深啊！这个在leetcode原题目里有个精确度，所以给了很大提示。
1. 找出最大最小值；
2. 误差没达到就一直二分；
3. 二分条件： 如果在循环找符合条件的mid的时候，只要一条符合就返回true，所有都不符合，说明mid设置太大了，真正的均值，在mid左侧。
4. 开始以为check函数要存在一个数组里，把算出来的num[i]-mid，后来发现我们就不用maintain这个数组，在循环里，保持一个pre的指针一直里sum，k个远，然后pre指针的数是pre之前所有求和数的最小值就行，min_sum = Math.min(prev, min_sum)。就这一句简单的话，就把>k这个给破了，高！
http://bookshadow.com/weblog/2017/07/16/leetcode-maximum-average-subarray-ii/
初始令lo = min(nums)，hi = max(nums) 令mid = hi, lastMid = lo 循环直到mid - lastMid < 1e-5： 令lastMid = mid，mid = (lo + hi) / 2 若一趟遍历检查发现nums中存在长度不小于k的连续子数组，并且均值>= mid：令lo = mid 否则：令hi = mid 返回mid
https://leetcode.com/articles/maximum-average-subarray-ii/
Time complexity : $O(nlog(max\_val-min\_val))$. $check$ takes $O(n)$ time and it is executed $O(log(max\_val-min\_val))$ times.
But, in this case, we need to find the maximum average of a subarray with atleast $k$ elements. The idea in this method is to try to approximate(guess) the solution and to try to find if this solution really exists. If it exists, we can continue trying to approximate the solution even to a further precise value, but choosing a larger number as the next approximation. But, if the initial guess is wrong, and the initial maximum average value(guessed) isn't possible, we need to try with a smaller number as the next approximate.

    public double findMaxAverage(int[] nums, int k) {
        double max_val = Integer.MIN_VALUE;
        double min_val = Integer.MAX_VALUE;
        for (int n: nums) {
            max_val = Math.max(max_val, n);
            min_val = Math.min(min_val, n);
        }
        double prev_mid = max_val, error = Integer.MAX_VALUE;
        while (error > 0.00001) {
            double mid = (max_val + min_val) * 0.5;
            if (check(nums, mid, k))
                min_val = mid;
            else
                max_val = mid;
            error = Math.abs(prev_mid - mid);
            prev_mid = mid;
        }
        return min_val;
    }
    public boolean check(int[] nums, double mid, int k) {
        double sum = 0, prev = 0, min_sum = 0;
        for (int i = 0; i < k; i++)
            sum += nums[i] - mid;
        if (sum >= 0)
            return true;
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - mid;
            prev += nums[i - k] - mid;
            min_sum = Math.min(prev, min_sum);
            if (sum >= min_sum)
                return true;
        }
        return false;
    }

https://discuss.leetcode.com/topic/96228/clean-c-binary-search-solution-with-explanation

The idea is using the binary search to find the maximum average value. We know that the maximum average value must be between the minimal value (left in the code ) and maximum value (right in the code ) in nums. Each time we can check if mid = (left+right)/2 is larger or less than the the maximum average value:

we use max_ave to denote the maximum average value. Then, for any i, j (j-i>=k-1), we can have (nums[i] - max_ave) + (nums[i+1] - max_ave)+...+ (nums[j] - max_ave) <=0. Therefore, for some i, j (j-i>=k-1), if we find (nums[i] - mid) + (nums[i+1] - mid)+...+ (nums[j] - mid) >0, then mid must be smaller than max_ave. The code is as follows:

    double findMaxAverage(vector<int>& nums, int k) {
        double left = INT_MAX, right = INT_MIN, mid;
        for(int num:nums){
            right = max(right, double(num));
            left = min(left, double(num));
        }
        while(left + 0.00001 < right){
            mid = left + (right - left)/2;
            if(islarger(nums, mid, k))right = mid;
            else left = mid;
        }
        return left;
    }
    
    //Return true when mid is larger than or equal to the maximum average value;
    //Return false when mid is smaller than the maximum average value.
    bool islarger(vector<int>& nums, double mid, int k){
        // sum: the sum from nums[0] to nums[i];
        // prev_sum:  the sum from nums[0] to nums[i-k];
        // min_sum: the minimal sum from nums[0] to nums[j] ( 0=< j  <= i-k );
        double sum = 0, prev_sum = 0, min_sum = 0;
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i] - mid;
            if(i >= k){
                prev_sum += nums[i-k] - mid;                        
                min_sum = min(prev_sum, min_sum); 
            }
            if(i >= k-1 && sum > min_sum)return false;
        }
        return true;                                               
    }

https://discuss.leetcode.com/topic/96123/java-solution-o-nlogm-binary-search-the-answer
(nums[i]+nums[i+1]+...+nums[j])/(j-i+1)>x
=>nums[i]+nums[i+1]+...+nums[j]>x*(j-i+1)
=>(nums[i]-x)+(nums[i+1]-x)+...+(nums[j]-x)>0

    boolean check(int[] nums,int k,double x) //Check whether we can find a subarray whose average is bigger than x
    {
        int n=nums.length;
        double[] a=new double[n];
        for (int i=0;i<n;i++) a[i]=nums[i]-x; //Transfer to a[i], find whether there is a subarray whose sum is bigger than 0
        double now=0,last=0;
        for (int i=0;i<k;i++) now+=a[i];
        if (now>=0) return true;
        for (int i=k;i<n;i++)
        {
            now+=a[i];
            last+=a[i-k];
            if (last<0) 
            {
                now-=last;
                last=0;
            }
            if (now>=0) return true;
        }
        return false;
    }
    public double findMaxAverage(int[] nums, int k) {
        double l=Integer.MIN_VALUE,r=Integer.MAX_VALUE;
        while (r-l>0.000004) //Binary search the answer
        {
            double mid=(l+r)/2;
            if (check(nums,k,mid)) l=mid; else r=mid;
        }
        return r;
    }

http://blog.csdn.net/u014688145/article/details/75260687

在第一题做法的基础上，遍历k到nums.length，求出最大，时间复杂度为O(n2)，TLE了，此题技巧性比较强，先用二分搜索解，把问题转换成求符合条件的subArray。什么样的subArray符合条件？

此类问题关键在于求最大的average，所以可以写出公式：

(ai+ai+1+⋯+aj)/(j−i+1)<=ans

所以，只要找到最大的ans使得对所有的ai到aj都符合上述约束即可，这就意味着一旦出现：

(ai+ai+1+⋯+aj)/(j−i+1)>ans

即不符合最大average的定义，我们只要在给定ans的情况下，找出这种状态即可，另外一方面，在所有符合状态的ans中，不断扩大ans，即能求出最大的ans。

令 k = j - i + 1，所以问题转变成：

(ai−ans)+⋯+(aj−ans)>0

的搜索，这里有了所谓的优化技巧，原本O(n2)的复杂度，在这个问题下，可以简化成O(n)，为何？

时间复杂度下降的原因在于，并非需要遍历所有可能的长度，即k从nums.length的每个subArray无需全部遍历。利用滑动窗口可以优化，在窗口增大的过程中，维护一个左侧小于0的subArray，这样得到的sum一定是当前下标下，所有窗口长度的最大sum，

符合窗口性质的搜索，大大简化了时间复杂度，或者换句话说，这里充分利用了窗口变动之后，累计计算的一些值，实在是高明。

http://blog.csdn.net/zjucor/article/details/75199933

思路：有2个trick

1. 只要满足一定误差，所以用二分，直接二分最后的平均值

2. 在判断某个平均值是否满足时，转换为求连续子数组的和大于0（这个求平均值的套路可以记一下）

1.     public double findMaxAverage(int[] nums, int k) {  
2.         int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;  
3.         for(int i : nums) {  
4.             min = Math.min(min, i);  
5.             max = Math.max(max, i);  
6.         }  
7.           
8.         double lo = min, hi = max;  
9.         while(hi-lo > 1e-6) {  
10.             double mid = (lo+hi)/2.0;  
11.             if(ok(nums, k ,mid))  
12.                 lo = mid;  
13.             else  
14.                 hi = mid;  
15.         }  
16.           
17.         return lo;  
18.     }  
19.   
20.     private boolean ok(int[] nums, int k, double mid) {  
21.         // 数组每个数减去mid，转换为：连续子数组累加大于0  
22.         double[] t = new double[nums.length];  
23.         for(int i=0; i<nums.length; i++)  
24.             t[i] = nums[i] - mid;  
25.           
26.         double sum = 0;  
27.         for(int i=0; i<k; i++)   sum += t[i];  
28.         if(sum >= 0) return true;  
29.           
30.         double min = 0, sum2 = 0;  
31.         for(int i=k; i<t.length; i++) {  
32.             sum2 += t[i-k];  
33.             sum += t[i];  
34.             min = Math.min(min, sum2);  
35.               
36.             if(sum - min >= 0)   return true;      
37.         }  
38.           
39.         return false;  
40.     }

https://www.jiuzhang.com/solution/maximum-average-subarray/
https://www.jiuzhang.com/solution/maximum-average-subarray-ii/

    private boolean canFind(int[] A, int K, double avg) {
        int i, k;
        double rightSum = 0, leftSum = 0, minLeftSum = 0;
        for (i = 0; i < K; ++i) {
            rightSum += A[i] - avg;
        }
        
        for (i = K; i <= A.length; ++i) {
            if (rightSum - minLeftSum >= 0) {
                return true;
            }
            
            if (i < A.length) {
                rightSum += A[i] - avg;
                leftSum += A[i - K] - avg;
                minLeftSum = Math.min(minLeftSum, leftSum);
            }
        }
        
        return false;
    } 
     
    public double maxAverage(int[] A, int K) {
        int i;
        double start, stop, mid;
        start = stop = A[0];
        for (i = 0; i < A.length; ++i) {
            start = Math.min(A[i], start);
            stop = Math.max(A[i], stop);
        }
        
        while (start + 1e-5 < stop) {
            mid = (start + stop) / 2;
            if (canFind(A, K, mid)) {
                start = mid;
            }
            else {
                stop = mid;
            }
        }
        
        return start;
    }

1

    public double maxAverage(int[] nums, int k) {
        // Write your code here
        double l = Integer.MAX_VALUE, r = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] < l)
                l = nums[i];
            if (nums[i] > r)
                r = nums[i];
        }
        
       
        while (r - l >= 1e-6) {
            double mid = (l + r) / 2.0;

            if (check_valid(nums, mid, k)) {
                l = mid;
            }
            else {
                r = mid;
            }
        }

        return l;
    }
    
    private boolean check_valid(int nums[], double mid, int k) {
        int n = nums.length;
        double min_pre = 0;
        double[] sum = new double[n + 1];
        sum[0] = 0; 
        for (int i = 1; i <= n; ++i) {
            sum[i] = sum[i - 1] + nums[i - 1] - mid;
            if (i >= k && sum[i] - min_pre >= 0) {
                return true;
            }
            if (i >= k)
                min_pre = Math.min(min_pre, sum[i - k + 1]);
        }
        return false;
    }

X.
https://discuss.leetcode.com/topic/96131/python-advanced-o-n-solution-convex-hull-window
X. http://www.cnblogs.com/grandyang/p/8021421.html

    double findMaxAverage(vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> sums(n + 1, 0);
        double left = *min_element(nums.begin(), nums.end());
        double right = *max_element(nums.begin(), nums.end());
        while (right - left > 1e-5) {
            double minSum = 0, mid = left + (right - left) / 2;
            bool check = false;
            for (int i = 1; i <= n; ++i) {
                sums[i] = sums[i - 1] + nums[i - 1] - mid;
                if (i >= k) {
                    minSum = min(minSum, sums[i - k]);
                }
                if (i >= k && sums[i] > minSum) {check = true; break;} 
            }
            if (check) left = mid;
            else right = mid;
        }
        return left;
    }

下面这种解法对上面的方法优化了空间复杂度 ，使用preSum和sum来代替数组，思路和上面完全一样，可以参加上面的讲解，注意这里我们的第二个if中是判断i >= k - 1，而上面的方法是判断i >= k，这是因为上面的sums数组初始化了n + 1个元素，注意坐标的转换，而第一个if中i >= k不变是因为j和i之间就差了k个，所以不需要考虑坐标的转换

X. Brute Force
https://leetcode.com/articles/maximum-average-subarray-ii/

• Time complexity : $O(n^2)$. Two for loops iterating over the whole length of $nums$ with $n$ elements.

    public double findMaxAverage(int[] nums, int k) {
        double res = Integer.MIN_VALUE;
        for (int s = 0; s < nums.length - k + 1; s++) {
            long sum = 0;
            for (int i = s; i < nums.length; i++) {
                sum += nums[i];
                if (i - s + 1 >= k)
                    res = Math.max(res, sum * 1.0 / (i - s + 1));
            }
        }
        return res;
    }

https://leetcode.com/problems/maximum-average-subarray-i

Given an array consisting of n integers, find the contiguous subarray of given length 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: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

1. 1 <= k <= n <= 30,000.
2. Elements of the given array will be in the range [-10,000, 10,000].

http://blog.csdn.net/u014688145/article/details/75260687

求连续和的最大值，两种做法，滑动窗口法，和累加和法。

滑动窗口法：

public double findMaxAverage(int[] nums, int k) { int sum = 0; for (int i = 0; i < k; ++i){ sum += nums[i]; } double max = sum / (1.0 * k); for (int i = 0; i < nums.length - k; ++i){ sum -= nums[i]; sum += nums[i + k]; max = Math.max(max, sum / (1.0 * k)); } return max; }

累加和法：

public double findMaxAverage(int[] nums, int k) { int[] sums = new int[nums.length + 1]; for (int i = 0; i < nums.length; ++i){ sums[i + 1] = sums[i] + nums[i]; } double max = Double.NEGATIVE_INFINITY; for (int i = 0; i + k < sums.length; ++i){ max = Math.max(max, (sums[i + k] - sums[i]) / (1.0 * k)); } return max; }
https://discuss.leetcode.com/topic/96154/java-solution-sum-of-sliding-window

    public double findMaxAverage(int[] nums, int k) {
        long sum = 0;
        for (int i = 0; i < k; i++) sum += nums[i];
        long max = sum;
        
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - nums[i - k];
            max = Math.max(max, sum);
        }
        
        return max / 1.0 / k;
    }

https://discuss.leetcode.com/topic/96066/simple-java-solution-sliding-window

    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        for(int i = 0; i < k; i++) {
            sum += nums[i];
        }
        
        int maxSum = sum;
        for(int i = 0, j = k; j < nums.length; i++, j++) {
            sum = sum - nums[i] + nums[j];
            maxSum = Math.max(sum, maxSum);
        }
        
        return ((double) maxSum) / ((double) k);
    }

https://discuss.leetcode.com/topic/96158/java-8-2-lines-using-reduce-w-explanation

Java 8's reduce functional feature comes in handy when we have to go through an array and calculate a result out of its contents. This solution is a bit more convoluted than the straightforward approach of using a for loop, but its a good way to look at the reduce function for single pass array problems.

The trick in using the reduce function boils down to following:

1. As we look at every element in the array, we need to access two information,
   • the rolling sum
   • the max sum
     These are the two variables we can maintain as the accumulator, that gets passed down to each iteration.
2. When using Java's reduce and to reduce the integer array to anything other than the type of the array, we need to use the 3 parameter version of reduce.

which is

<U> U reduce(U identity,
         BiFunction<U,? super T,U> accumulator,
         BinaryOperator<U> combiner)

• identity refers to the initial value of the accumulator, in our case, we are going to accumulate both sum and maxSum in an integer[].
• accumulator, is a Function that takes the
  • the same integer array that gets passed down through each iteration which is the acc int[]
  • and returns the new integer[], which will contain the updated sum and the updated maxSum
• combiner is not used unless we have a parallel stream, so its of no significance in this context

public static double findMaxAverage(int[] nums, int k) {
        int sum = IntStream.range(0, k).map(i -> nums[i]).sum();
        return IntStream.range(k, nums.length).boxed().reduce(
                new int[] {sum - nums[0], sum},
                (arr, i) -> new int[] {arr[0] + nums[i] - nums[i-k+1], Math.max(arr[1], arr[0] + nums[i])},
                (x, y) -> x)[1] / (double)k;

    }