# Java O(n) soution (Convex Hull Window)

• The original post and python solution by @awice is here

I just convert it to the java version

``````public class Solution {
//convex hull window
public double findMaxAverage(int[] nums, int k) {
int n = nums.length;
long[] sum = new long[n+1];

for(int i = 0; i < n; i++){
sum[i+1] = sum[i] + nums[i];
}

double ans = Integer.MIN_VALUE;

for(int j = k - 1; j < n; j++){
while(hull.size() >= 2 && getAvg(sum, hull.get(hull.size() - 2), hull.get(hull.size() - 1) - 1) >= getAvg(sum, hull.get(hull.size() - 2), j-k)){
hull.remove(hull.size() - 1);
}

hull.add(j - k + 1);
while(hull.size() >= 2 && getAvg(sum, hull.get(0), hull.get(1) - 1) <= getAvg(sum, hull.get(0), j)){
hull.removeFirst();
}

ans = Math.max(ans, getAvg(sum, hull.getFirst(), j));
}

return ans;
}

private double getAvg(long[] sum, int i, int j){
return (sum[j+1] - sum[i])/(double) (j+1-i);
}
}
``````

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