Start with the brute force O(n^2) solution, where we check each range of size >= k. The sum of values in that range can be calculated from running sums.

Now observe that we only need to check ranges of size k, k+1, ... 2k-1.

For any larger range, it can be partitioned into two smaller sub-ranges of size >= k, and one of these sub-ranges will have average at least as good.

```
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double res= -10000;
int k2=k*2-1;
vector<int> lsum (nums.size());
lsum[0]=nums[0];
for (int i=1;i<nums.size();++i){
lsum [i] = lsum[i-1] +nums[i];
}
for(int i=0;i<nums.size();++i){
for(int d=k; i+d<=nums.size()&&d <=k2; ++d){
auto s = lsum[i+d-1];
if (i>0) s -= lsum[i-1];
if (res*d<=s) res = s*1.0/d;
}
}
return res;
}
};
```