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;
    }
}

results matching ""

    No results matching ""