Welcome to Subscribe On Youtube

644. Maximum Average Subarray II

Description

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is greater than or equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

 

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation:
- When the length is 4, averages are [0.5, 12.75, 10.5] and the maximum average is 12.75
- When the length is 5, averages are [10.4, 10.8] and the maximum average is 10.8
- When the length is 6, averages are [9.16667] and the maximum average is 9.16667
The maximum average is when we choose a subarray of length 4 (i.e., the sub array [12, -5, -6, 50]) which has the max average 12.75, so we return 12.75
Note that we do not consider the subarrays of length < 4.

Example 2:

Input: nums = [5], k = 1
Output: 5.00000

 

Constraints:

• n == nums.length
• 1 <= k <= n <= 104
• -104 <= nums[i] <= 104

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public double findMaxAverage(int[] nums, int k) {
          double eps = 1e-5;
          double l = 1e10, r = -1e10;
          for (int x : nums) {
              l = Math.min(l, x);
              r = Math.max(r, x);
          }
          while (r - l >= eps) {
              double mid = (l + r) / 2;
              if (check(nums, k, mid)) {
                  l = mid;
              } else {
                  r = mid;
              }
          }
          return l;
      }
  
      private boolean check(int[] nums, int k, double v) {
          double s = 0;
          for (int i = 0; i < k; ++i) {
              s += nums[i] - v;
          }
          if (s >= 0) {
              return true;
          }
          double t = 0;
          double mi = 0;
          for (int i = k; i < nums.length; ++i) {
              s += nums[i] - v;
              t += nums[i - k] - v;
              mi = Math.min(mi, t);
              if (s >= mi) {
                  return true;
              }
          }
          return false;
      }
  }
  

• class Solution {
  public:
      double findMaxAverage(vector<int>& nums, int k) {
          double eps = 1e-5;
          double l = *min_element(nums.begin(), nums.end());
          double r = *max_element(nums.begin(), nums.end());
          auto check = [&](double v) {
              double s = 0;
              for (int i = 0; i < k; ++i) {
                  s += nums[i] - v;
              }
              if (s >= 0) {
                  return true;
              }
              double t = 0;
              double mi = 0;
              for (int i = k; i < nums.size(); ++i) {
                  s += nums[i] - v;
                  t += nums[i - k] - v;
                  mi = min(mi, t);
                  if (s >= mi) {
                      return true;
                  }
              }
              return false;
          };
          while (r - l >= eps) {
              double mid = (l + r) / 2;
              if (check(mid)) {
                  l = mid;
              } else {
                  r = mid;
              }
          }
          return l;
      }
  };
  

• class Solution:
      def findMaxAverage(self, nums: List[int], k: int) -> float:
          def check(v: float) -> bool:
              s = sum(nums[:k]) - k * v
              if s >= 0:
                  return True
              t = mi = 0
              for i in range(k, len(nums)):
                  s += nums[i] - v
                  t += nums[i - k] - v
                  mi = min(mi, t)
                  if s >= mi:
                      return True
              return False
  
          eps = 1e-5
          l, r = min(nums), max(nums)
          while r - l >= eps:
              mid = (l + r) / 2
              if check(mid):
                  l = mid
              else:
                  r = mid
          return l
  
  

• func findMaxAverage(nums []int, k int) float64 {
  	eps := 1e-5
  	l := float64(slices.Min(nums))
  	r := float64(slices.Max(nums))
  	check := func(v float64) bool {
  		s := 0.0
  		for _, x := range nums[:k] {
  			s += float64(x) - v
  		}
  		if s >= 0 {
  			return true
  		}
  		t := 0.0
  		mi := 0.0
  		for i := k; i < len(nums); i++ {
  			s += float64(nums[i]) - v
  			t += float64(nums[i-k]) - v
  			mi = math.Min(mi, t)
  			if s >= mi {
  				return true
  			}
  		}
  		return false
  	}
  	for r-l >= eps {
  		mid := (l + r) / 2
  		if check(mid) {
  			l = mid
  		} else {
  			r = mid
  		}
  	}
  	return l
  }
  

• function findMaxAverage(nums: number[], k: number): number {
      const eps = 1e-5;
      let l = Math.min(...nums);
      let r = Math.max(...nums);
      const check = (v: number): boolean => {
          let s = nums.slice(0, k).reduce((a, b) => a + b) - v * k;
          if (s >= 0) {
              return true;
          }
          let t = 0;
          let mi = 0;
          for (let i = k; i < nums.length; ++i) {
              s += nums[i] - v;
              t += nums[i - k] - v;
              mi = Math.min(mi, t);
              if (s >= mi) {
                  return true;
              }
          }
          return false;
      };
      while (r - l >= eps) {
          const mid = (l + r) / 2;
          if (check(mid)) {
              l = mid;
          } else {
              r = mid;
          }
      }
      return l;
  }
  
  

All Problems

All Solutions