Maximum Average Subarray II

Given an array with positive and negative numbers, find the maximum average subarray which length should be greater or equal to given length k.

思路：

对平均值进行二分。一个数组平均的最大不会超过数组最大值，也不会低于数组最小值。也就是说，这个平均值肯定在数组最大值和最小值的范围区间内。

用前缀和数组判断是否数组中是否有一段长度大于等于k的子数组，平均数大于等于mid。如果存在，就把left=mid，如果不存在就把right=mid。这样不断所有l和r的距离，直到重合。left 就是所能找到的最大平均值。

复杂度：

时间： O(nlog(max_val−min_val))O(nlog(max_val−min_val))

空间：O(n)

public double maxAverage(int[] nums, int k) {

       double result = 0.0;

        if(nums == null || nums.length < k) {

             return result;

         }

         double l = Integer.MAX_VALUE;

         double r = Integer.MIN_VALUE;

         //find the largest number and smallest number in the array

          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 average, 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) {

             // 原数组中的每一个数减去这个mid

                  sum[i] = sum[i - 1] + nums[i - 1] - average;

                 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;

  }