# C++ solution O(nm) whose result is accurate.(m is related to the nums)

• ``````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;
}
``````

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

• @Hao-Cai The running time is round 100ms, at least beats 90%. The time of binary search is almost same. But the result is more accurate. Of course, both methods satisfy the 10-5 requirment.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.