Maximum Average Subarray - lintcode

Given an array with positive and negative numbers, find themaximum average subarraywhich length should be greater or equal to given lengthk.

Example

Given nums =[1, 12, -5, -6, 50, 3], k =3

Return15.667// (-6 + 50 + 3) / 3 = 15.667

Analysis: find the maximum average subarray for equal to given length K is much simpler problem. However, here we need to find the answer for subarray with length >= K. We binary search the maximum average knowing that the maximum average should always within the range of the min and max element of the array.

A
lso let maxaverage being in the internaval of (l, r) and let P being the array, the average of the subarray of length k is ( P[i-k+1]+..+P[i] ) / k, so if there is a potential_max_average in (l,r) with which

P[i-k+1]+..+P[i] >= potential_max_average * k

(P[i-k+1] - potential_max_average ) + .. + (P[i] - potential_max_average ) >= 0

then potential_max_average is a valid potential max average, and the max_average is [potential_max_average , r], otherwise, it is [l, potential_max_average).

Solution

public double maxAverage(int[] nums, int k) {
    if (nums.length == 0){
        return 0.0;
    }

    double l = Integer.MAX_VALUE;
    double r = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++){
        if (nums[i] < l){
            l = nums[i];
        }

        if (nums[i] > r){
            r = nums[i];
        }
    }

    double[] sum = new double[nums.length + 1];        
    while (r - l > 1e-6){
        double mid = (r + l) / 2; 
        boolean toRight = false;
        double prev_k_elem_sum = 0.0;

        for (int i = 1; i <= nums.length; i++){
            sum[i] = sum[i-1] + nums[i-1] - mid;

            if (i >= k){                    
                if (sum[i] - prev_k_elem_sum >= 0){
                    toRight = true;
                    break;
                } 
                prev_k_elem_sum = Math.min(prev_k_elem_sum, sum[i-k+1]);
            }
        }

        if (toRight){
            l = mid;
        } else {
            r = mid;
        }   
    }
    return toPrecision(l, 3);
}

public double toPrecision(double val, int precision){
    val *= Math.pow(10, precision);
    val = Math.round(val);
    val /= Math.pow(10, precision);
    return val;
}