Tuesday, September 5, 2017

643. Maximum Average Subarray I

https://leetcode.com/problems/maximum-average-subarray-i/description/
Solution 1. Sliding window.
double findMaxAverage(vector<int>& nums, int k) {
        int start = 0, end = 0, sum = 0, res = INT_MIN;
        while(end < nums.size()) {
            sum += nums[end];
            if(end - start + 1 == k) {
                res = max(sum, res);
                sum -= nums[start++];
            }
            end++;
        }
        return (double)res/(double)k;
    }
or,
    double findMaxAverage(vector<int>& nums, int k) {
        int mx = 0, s = 0, i = 0, j = 0;
        for(j=0; j<k; j++) s += nums[j];
        mx = s;
        while(j < nums.size()) {
            s = s - nums[i++] + nums[j++];
            mx = max(mx, s);
        }
        return double(mx)/k;
    }

No comments:

Post a Comment