4-liner O(N) time and O(1) space


  • 0
        double findMaxAverage(vector<int>& a, int k) 
        {
            // max sum of k consecutive elements
            int maxkSum = accumulate(a.begin(), a.begin()+k, 0);
            
            for (int i = k, ksum = maxkSum; i < a.size(); ++i)
                maxkSum = max(maxkSum, ksum += (a[i]-a[i-k]));
            
            return maxkSum/(double)k;
        }
    

Log in to reply
 

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