public class Solution {

    /**

     * @param nums: an array with positive and negative numbers

     * @param k: an integer

     * @return: the maximum average

     */

    private boolean canFind(int[] nums, int k, double avg) {

        double rightSum = 0, leftSum = 0, minLeftSum = 0;

        for (int i = 0; i < k; i++) {

            rightSum += nums[i] - avg;

        }

        for (int i = k; i <= nums.length; i++) {

            if (rightSum - minLeftSum >= 0) {

                return true;

            }

            if (i < nums.length) {

                rightSum += nums[i] - avg;

                leftSum += nums[i - k] - avg;

                minLeftSum = Math.min(minLeftSum, leftSum);

            }

        }

        return false;

    }

    public double maxAverage(int[] nums, int k) {

        double start, end, mid;

        start = end = nums[0];

        for (int i = 0; i < nums.length; i++) {

            start = Math.min(nums[i], start);

            end = Math.max(nums[i], end);

        }

        while (start + 1e-5 < end) {

            mid = (start + end) / 2;

            if (canFind(nums, k, mid)) {

                start = mid;

            } else {

                end = mid;

            }

        }

        return start;

    }

}