Maximum Average Subarray II
ID: 617; medium; 子数组的最大平均值 II
Solution 1 (Java)
public class Solution {
/**
* @param nums: an array with positive and negative numbers
* @param k: an integer
* @return: the maximum average
*/
public double maxAverage(int[] nums, int k) {
if (nums == null || nums.length == 0 || k > nums.length)
return -1;
double left, right, mid;
left = right = nums[0];
double delta = 1e-6;
for (int n : nums) {
left = Math.min(n, left);
right = Math.max(n, right);
}
while (left + delta < right) {
mid = left + (right - left) / 2;
if (isAverageValid(nums, mid, k)) {
left = mid;
} else {
right = mid;
}
}
return isAverageValid(nums, right, k) ? right : left;
}
private boolean isAverageValid(int[] nums, double avg, int k) {
double sum = 0, leftSum = 0, leftSumMin = 0;
for (int i = 0; i < nums.length; i++) {
// sum is the sum of elements from 0 to i
sum += nums[i] - avg;
if (i >= k - 1 && sum >= 0) return true;
if (i >= k) {
// left sum is the sum of elements from 0 to i-k
leftSum += nums[i - k] - avg;
leftSumMin = Math.min(leftSumMin, leftSum);
// difference here is the max value for a k-length array
if (sum - leftSumMin >= 0)
return true;
}
}
return false;
}
}
Last updated