Maximum Average Subarray I

Problem

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

Constraints

• n == nums.length
• 1 <= k <= n <= 105
• -104 <= nums[i] <= 104

Solution

The problem Maximum Average Subarray I can be solved using a sliding window technique. By adding a new element to the window and removing the oldest element from it for every elements in the array, it is possible to find the maximum average value in a single iteration of the array.

Implementation

class Solution
{
  public:
    double findMaxAverage(vector<int> &nums, int k)
    {
        int sum = 0;
        for (int i = 0; i < k; i++)
            sum += nums[i];

        int ret = sum;
        for (int i = k; i < nums.size(); i++)
        {
            sum += nums[i] - nums[i - k];
            ret = max(ret, sum);
        }

        return (double)ret / k;
    }
};