Maximum Average Subarray

Question

from lintcode

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

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

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

Return 15.667 // (-6 + 50 + 3) / 3 = 15.667

Idea

I hate this question. This is really a challenge of mathematics rather than coding skills. I think I need to write an article to explain the solution. Right now I will just put them into code comments. In short, you try to guess an answer that is close enough to the real answer in terms of precision by binary search.

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) {
        int n = nums.length;
        double left = Integer.MAX_VALUE, right = Integer.MIN_VALUE;
        // find largest and smallest
        for (int i = 0; i < n; i++) {
            left = Math.min(left, (double)nums[i]);
            right = Math.max(right, (double)nums[i]);
        }

        double[] sumDiff = new double[n + 1];
        sumDiff[0] = 0;

        // When the error is big, keep seaching
        while (right - left > 1e-6) {
            // assume guessMaxAvg is the maximum average
            double guessMaxAvg = (left + right) / 2;

            // GOAL: maintain an array such that
            // sumDiff[i + 1] = sum(nums[0] ... nums[i]) - (len(0 .. i) * guessMaxAvg)
            // where 0 <= i < nums.length
            for (int i = 0; i < n; i++) {
                // math trick: difference of sum - sumAvg == n * (each element - average)
                // and we can add them incrementally
                sumDiff[i + 1] = sumDiff[i] + (nums[i] - guessMaxAvg);
            }

            double minTrunk = 0;
            double diffMax = Integer.MIN_VALUE;

            for (int i = k; i <= n; i++) {
                /**
                 *  explanation:
                 *    since sumDiff[i] represents `difference(sum elements, sum average) from 0 to (i - 1)`
                 *    then how to get `difference(sum elements, sum average) between (i - 1) - k + 1 to (i - 1)` ?
                 *    ans: MINUS `difference(sum elements, sum average) from 0 to (i - 1) - k`, i.e.
                 *    minus sumDiff[((i - 1) - k) + 1] = sumDiff[i - k]
                 *
                 *    So we got sumDiff(position x to y) = sumDiff(position 0 to y) - sumDiff(position 0 to x - 1)
                 *      = sumDiff[y + 1] - sumDiff[x]
                 *    I want to find the largest sumDiff(position x to y)
                 *    That means I want the minimal sumDiff[x].
                 *    For each sumDiff[y + 1], the possible x ranges from 0 to (y + 1) - k so that
                 *    number of elements between x to y is larger equals than k.
                 *    Let's pick the minimum to minus.
                 */
                minTrunk = Math.min(minTrunk, sumDiff[i - k]);
                diffMax = Math.max(diffMax, sumDiff[i] - minTrunk);
            }
            if (diffMax >= 0) {
                /**
                 * That means there exists a segment from x to y,
                 * where the average is larger than our guess answer.
                 * and thus makes the diffMax positive.
                 *
                 * In this case, we re-guess from guessMaxAvg to right
                 */
                left = guessMaxAvg;
            }
            else {
                right = guessMaxAvg;
            }
        }
        /**
         *  The error is small enough, is okay to return either left or right
         */
        return left;
    }
}