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


  • 0
    A

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

Log in to reply
 

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