C++ solution (looks like prime number filtering)

  • 0
    class Solution {
        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;
            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;

Log in to reply

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