# share simple java solution O(nlog(K))based on discussion with my friend! K is range of vlaues

• The basic idea is to use binary check. Since the values range is from [-10000,10000], so we can set low=-10000, and high=10000 firstly, then use binary search to check whether we can find a subarray (length>=k) whose average is larger than the target value, where target value is equal to (low+high)/2 every time. After every check, we need to reset low and high value based on checking result. Since the final answer error will be 10^-5, so we can repeat 100 times to make sure our final return value' calculation error will be less than 10^-5 . Here is java solution:

``````public class Solution {
public double findMaxAverage(int[] nums, int k) {
double low=-100000;
double high=100000;

int rep=0;
while(low<high&&rep<100){
double mid=(low+high)/2;
if(check(nums,k,mid)){
low=mid;
}else{
high=mid;
}

rep++;
}

return low;
}

public boolean check(int[] nums,int k,double target){
double[] values = new double[nums.length];
for(int i=0;i<nums.length;i++){
values[i]=(double)nums[i]-target;
}

double sum=0;
double pre_min=0;
double pre_sum=0;

for(int i=0;i<values.length;i++){
sum+=values[i];
if(i>=k-1){
if(sum-pre_min>=0){
return true;
}
pre_sum+=values[i-(k-1)];
pre_min=Math.min(pre_sum,pre_min);
}
}

return false;
}
}
``````

• 100000

nice solution! but i do not know how to calculate the number 100 to make sure less than 10^-5 ,can you explain please？

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.