double findMaxAverage(vector<int>& nums, int k) {
int i, j;
vector<int> cumsum(nums.size() + 1, 0);
vector<int> index(nums.size(), 0);
vector<double> average(nums.size(), 0.0);
double temp, result = INT_MIN;
// cumulate sum
for(i = 0; i < nums.size(); i++) cumsum[i + 1] = cumsum[i] + nums[i];
// calculate the maximum average end with the i_th num, the length is unlimited
for(i = 0; i < nums.size()  k; i++) {
index[i] = i;
average[i] = nums[i];
j = i  1;
while(j >= 0 && average[j] >= average[i]) {
average[i] = (cumsum[i + 1]  cumsum[index[j]]) / (i  index[j] + 1.0);
index[i] = index[j];
j = index[j]  1;
}
}
// calculate the maximum average end with the i_th num, the length is greater than or equal to k
for(i = k  1; i < nums.size(); i++) {
temp = double(cumsum[i + 1]  cumsum[i  k + 1]) / k;
j = i  k;
while(j >= 0 && average[j] >= temp) {
temp = (cumsum[i + 1]  cumsum[index[j]]) / (i  index[j] + 1.0);
j = index[j]  1;
}
result = temp > result ? temp : result;
}
return result;
}
C++ solution O(nm) whose result is accurate.(m is related to the nums)


@kevincabbage
What is the running time? I guess it might be better if using the binary search.