|
| 1 | +package com.fishercoder.solutions; |
| 2 | + |
| 3 | +/** |
| 4 | + * 644. Maximum Average Subarray II |
| 5 | + * |
| 6 | + * Given an array consisting of n integers, find the contiguous subarray whose length is greater than |
| 7 | + * or equal to k that has the maximum average value. And you need to output the maximum average value. |
| 8 | +
|
| 9 | + Example 1: |
| 10 | + Input: [1,12,-5,-6,50,3], k = 4 |
| 11 | + Output: 12.75 |
| 12 | + Explanation: |
| 13 | + when length is 5, maximum average value is 10.8, |
| 14 | + when length is 6, maximum average value is 9.16667. |
| 15 | + Thus return 12.75. |
| 16 | +
|
| 17 | + Note: |
| 18 | + 1 <= k <= n <= 10,000. |
| 19 | + Elements of the given array will be in range [-10,000, 10,000]. |
| 20 | + The answer with the calculation error less than 10-5 will be accepted. |
| 21 | + */ |
| 22 | +public class _644 { |
| 23 | + /**reference: https://leetcode.com/articles/maximum-average-subarray-ii/#approach-2-using-binary-search-accepted |
| 24 | + * https://discuss.leetcode.com/topic/96123/java-solution-o-nlogm-binary-search-the-answer/13*/ |
| 25 | + |
| 26 | + /**To understand the idea behind this method, let's look at the following points. |
| 27 | + * Firstly, we know that the value of the average could lie between the range (min, max)(min,max). |
| 28 | + * Here, minmin and maxmax refer to the minimum and the maximum values out of the given numsnums array. |
| 29 | + * This is because, the average can't be lesser than the minimum value and can't be larger than the maximum value. |
| 30 | + But, in this case, we need to find the maximum average of a subarray with atleast kk elements. |
| 31 | + The idea in this method is to try to approximate(guess) the solution and to try to find if this solution really exists. |
| 32 | + If it exists, we can continue trying to approximate the solution even to a further precise value, |
| 33 | + but choosing a larger number as the next approximation. |
| 34 | + But, if the initial guess is wrong, and the initial maximum average value(guessed) isn't possible, |
| 35 | + we need to try with a smaller number as the next approximate. |
| 36 | +
|
| 37 | + Now, instead of doing the guesses randomly, we can make use of Binary Search. |
| 38 | + With minmin and maxmax as the initial numbers to begin with, |
| 39 | + we can find out the midmid of these two numbers given by (min+max)/2(min+max)/2. |
| 40 | + Now, we need to find if a subarray with length greater than or equal to kk is possible with an average sum greater than this midmid value. |
| 41 | + */ |
| 42 | + public double findMaxAverage(int[] nums, int k) { |
| 43 | + double l = -10000, r = 10000; |
| 44 | + while (r - l > 10e-7) { |
| 45 | + double mid = (l+r)/2; |
| 46 | + if (getMaxSubbaraySumOfSizeK(nums, k, mid) >= 0) { |
| 47 | + l = mid; |
| 48 | + } else { |
| 49 | + r = mid; |
| 50 | + } |
| 51 | + } |
| 52 | + return (l+r)/2; |
| 53 | + } |
| 54 | + |
| 55 | + private double getMaxSubbaraySumOfSizeK(int[] nums, int k, double mid) { |
| 56 | + double sum = 0.0; |
| 57 | + for (int i = 0; i <= k-1; i++) { |
| 58 | + sum += nums[i] - mid; |
| 59 | + } |
| 60 | + double maxSum = sum, prev = nums[0] - mid; |
| 61 | + for (int i = k; i < nums.length; i++) { |
| 62 | + sum = sum - nums[i-k] + nums[i]; |
| 63 | + maxSum = Math.max(maxSum, Math.max(sum, sum + prev)); |
| 64 | + prev = Math.max(nums[i-k+1], nums[i-k+1] + prev) - mid; |
| 65 | + } |
| 66 | + return maxSum; |
| 67 | + } |
| 68 | +} |
0 commit comments