643. Maximum Average Subarray I

1. Description

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.

2. Example

Example 1

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2

Input: nums = [5], k = 1
Output: 5.00000

3. Constraints

• n == nums.length
• 1 <= k <= n <= 10$^{5}$
• -10$^{4}$ <= nums[i] <= 10$^{4}$

4. Solutions

Sliding Window

n = nums.size()
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

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

        return max_average;
    }
};