[LintCode] Problem 617 - Maximum Average Subarray II

Posted on | In ,

Given an array with positive and negative numbers, find the maximum average subarray which length should be greater or equal to given length k.

Note

It’s guaranteed that the size of the array is greater or equal to k.

Example

No.1

Input:
[1,12,-5,-6,50,3]
3

Output:
15.667

Explanation:
(-6 + 50 + 3) / 3 = 15.667

No.2

Input:
[5]
1

Output:
5.000

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// (nums[i] + nums[i+1] + … + nums[j]) / (j-i+1) >= x
// =>(nums[i] - x) + (nums[i+1] - x) + … + (nums[j] - x) >= 0
public double maxAverage(int[] nums, int k) {
    double left = Double.MAX_VALUE;
    double right = Double.MIN_VALUE;

    for (int num : nums) {
        left = Math.min(left, num);
        right = Math.max(right, num);
    }

    while (right - left > 1e-5) {
        double mid = left + (right - left) / 2;

        if (isMidLarger(nums, k, mid))
            right = mid;
        else
            left = mid;

    }

    return left;
}

private boolean isMidLarger(int[] nums, int k, double mid) {
    double sum = 0;
    double preSum = 0;
    double minSum = 0;

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

        if (i >= k) {
            preSum += nums[i - k] - mid;
            minSum = Math.min(minSum, preSum);
        }

        if (i >= k - 1 && sum - minSum >= 0)
            return false;
    }

    return true;
}