Lintcode 617. Maximum Average Subarray II

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

Example

Example 1:

Input:
[1,12,-5,-6,50,3]
3
Output:
15.667
Explanation:
 (-6 + 50 + 3) / 3 = 15.667

Example 2:

Input:
[5]
1
Output:
5.000

Notice

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

Analysis:
Binary search for the result. Given a target average T, can we find out 
A[left] + ... A[right] / (right - left + 1) >= T. If we can find out this T, meaning the T we tried might be too small. We should try a bigger T. 

For  A[left] + ... A[right] / (right - left + 1) >= T, we can transform to 
(A[left] - T) + ... + (A[right] - T) >= 0
That is, For B[i] = A[i - 1], can we find out B[i] + ... + B[j] >= 0? This can be done by prefix sum. 


Code (Java):

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) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return 0;
        }
        
        double lo = nums[0];
        double hi = nums[0];
        for (int i = 0; i < nums.length; i++) {
            lo = Math.min(lo, nums[i]);
            hi = Math.max(hi, nums[i]);
        }
        
        while (lo + 1e-5 < hi) {
            double mid = lo + (hi - lo) / 2;
            if (canFind(nums, k, mid)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        
        return lo;
    }
    
    private boolean canFind(int[] nums, int k, double target) {
        double leftSum = 0;
        double rightSum = 0;
        double minLeftSum = 0;
        
        for (int i = 1; i <= nums.length; i++) {
            rightSum += nums[i - 1] - target;
            
            if (i >= k) {
                leftSum += i > k ? nums[i - k - 1] - target : 0;
                
                minLeftSum = Math.min(leftSum, minLeftSum);
            
                if (rightSum - minLeftSum >= 0) {
                    return true;
                }
            }
        }
        
        return false;
    }
}