Maximum Average Subarray

LintCode上的一道比较经典的二分搜索题，此题就是典型的二分答案而非二分数组的题目，下面简单描述思路

• 一个数组的最大平均数只可能是数组中最大数本身，这是很容易想到的
• 相应的，最小平均数也就只可能是最小数本身了，由此就确定了二分的上下界
• 因为此题是平均数，所以循环判定终止的条件设置为上界和下界的差小于某个特定值时（例如1e-6）
• 每次二分拿中间值去数组中比对，看有没有超过要求长度又能保证平均值的子数组（check函数）
• 在进行check时需要一个参考数组ref来记录prefix sum，同时需要一个min_pre变量来保存当前扫描过的符合要求的最小prefix sum（这一条是最tricky的地方）

代码如下：

class Solution:
    # @param {int[]} nums an array with positive and negative numbers
    # @param {int} k an integer
    # @return {double} the maximum average
    def maxAverage(self, nums, k):
        # Write your code here
        left, right = min(nums), max(nums)
        while right - left >= 1e-6:
            mid = left + (right - left) / 2.0
            if self.check(nums, mid, k):
                left = mid
            else:
                right = mid

        return left + (right - left) / 2

    def check(self, nums, mid, k):
        n = len(nums)
        ref = [0] * (n + 1)
        min_pre = 0

        for i in xrange(1, n + 1):
            ref[i] = ref[i - 1] + nums[i - 1] - mid
            if i >= k and ref[i] - min_pre >= 0:
                return True
            if i >= k:
                min_pre = min(min_pre, ref[i - k + 1])        # 除非min_pre本身小于当前坐标往前走k个数的prefix sum
                                                              # 否则就直接用ref[i - k + 1]因为这样取到了满足条件最短
        return False                                          # 的长度，这样更有可能找到目标