# C++ solution (looks like prime number filtering)

• ``````class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
vector<bool> f(nums.size()+1, true);
vector<int> sv(nums.size(), 0);
double ret = numeric_limits<double>::lowest();
int last_k=0;
while (k<=nums.size()) {
if (f[k]) { ret = max(ret, helper(nums, k, sv, last_k)); last_k = k; }
else { k++; continue; }
// The max average with i*k as step will not exceed the max average with k as step
// As the average of several numbers will not exceed the max of those numbers
// So we set the flags of the i*k to false.
for (int i=1; i*k<=nums.size(); i++) f[i*k] = false;
k++;
}
return ret;
}

double helper(vector<int>& nums, int k, vector<int> &sv, int last_k) {
double ret = numeric_limits<double>::lowest();
int gap = 0;
for (int i=last_k; i<k; i++) gap += nums[i];
sv[0] += gap;
ret = max(ret, (double)sv[0]/(double)k);
for (int i=1; i<nums.size()-k+1; i++) {
gap += nums[i+k-1] - nums[i+last_k-1];
sv[i] += gap;
ret = max(ret, (double)sv[i]/(double)k);
}
return ret;
}
};
``````

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