C++ solution, simple improvement to brute force, O(nk)

  • 1

    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 {
        double findMaxAverage(vector<int>& nums, int k) {
            double res= -10000;
            int k2=k*2-1;
            vector<int> lsum (nums.size());
            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;

Log in to reply

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