Maximum Average Subarray
[Problem description]( http://lintcode.com/en/problem/maximum-average-subarray/#\
Brute force 1: O(n^2)
public double maxAverage(int[] nums, int k) {
// Write your code here
double max = Double.NEGATIVE_INFINITY;
int len = nums.length;
double[] sum = new double[len + 1];
for(int i = 1; i < len + 1; i++){
sum[i] += sum[i - 1] + nums[i - 1];
}
for(int i = 0; i < len + 1; i++){
for(int j = i; j < len + 1; j++){
if(j - i < k){
continue;
}
double val = sum[j] - sum[i];
max = Math.max(max, val / (j - i));
}
}
return max;
}
Brute force 2: O(n^2)
public double maxAverage(int[] nums, int k) {
// Write your code here
double max = Double.NEGATIVE_INFINITY;
for(int i = 0; i < nums.length - k + 1; i++){
long sum = 0;
for(int j = i; j < nums.length; j++){
sum += nums[j];
if(j - i + 1 >= k){
max = Math.max(max, (double)sum / (j - i + 1));
}
}
}
return max;
}
The method above will all get Time Limit Exceeded Error.
There is a O(nlogn) solution:
[jiuzhang solution](http://www.jiuzhang.com/solution/maximum-average-subarray/\
[stackoverflow explenation](https://stackoverflow.com/questions/13093602/finding-subarray-with-maximum-sum-number-of-elements\
[another reference](http://blog.csdn.net/qq_34153219/article/details/56298842\
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) {
// Write your code here
double l = Integer.MAX_VALUE, r = Integer.MIN_VALUE;
for(int i = 0; i < nums.length; i++){
l = Math.min(l, nums[i]);
r = Math.max(r, nums[i]);
}
while(r - l > 1e-6){
double mid = (l + r) / 2.0;
if(isSmallMid(nums, mid, k)){
l = mid;
}else{
r = mid;
}
}
return l;
}
private boolean isSmallMid(int[] nums, double mid, int k){
int len = nums.length;
double[] sum = new double[len + 1];
double minPre = 0;
for(int i = 1; i < len + 1; i++){
sum[i] = sum[i - 1] + nums[i - 1] - mid;
if(i >= k && sum[i] - minPre >= 0){
return true;
}
if(i >= k){
minPre = Math.min(minPre, sum[i - k + 1]);
}
}
return false;
}
}