python version. took me a while to understand the validation part.

max(presum[j] - presum[i] - (sub array length)*mean)
= max(nums[i+1]-mean + nums[i+2]-mean + ... + nums[j]-mean)
= presum[j]-(sub array length)*mean - min(presum[i] - (sub array length)*mean)

min_pre_sum is initialized to 0, which means sum is from 0 to j. This is the base case.

class Solution(object):
def findMaxAverage(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: float
"""
if nums is None or len(nums)<k: return 0.0
l, h = min(nums), max(nums)
while l < h - 0.00001:
mid = l + (h-l)/2.0
if self.larger_than(nums, k, mid):
l = mid
else:
h = mid
return l
def larger_than(self, nums, k, mean):
sum_so_far = 0
for i in xrange(k):
sum_so_far += nums[i] - mean
if sum_so_far>=0:
return True
min_pre_sum = 0
pre_sum = 0
for i in xrange(k, len(nums)):
sum_so_far += nums[i] - mean
pre_sum += nums[i-k] - mean
min_pre_sum = min(min_pre_sum, pre_sum)
if sum_so_far >= min_pre_sum:
return True
return False