Maximum Average Subarray I Problem


Description

LeetCode Problem 643.

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.

Example 1:

1
2
3
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:

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

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double sum = 0, res = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            if (i < k) 
                sum += nums[i];
            else {
                res = max(sum, res);
                sum += nums[i] - nums[i-k];
            }
        }
        res = max(sum, res);
        return res / k;
    }
};




Related Posts

Fruit Into Baskets Problem

LeetCode 904. You are visiting a farm that has a...

Binary Subarrays With Sum Problem

LeetCode 930. Given a binary array nums and an integer...

Maximum Average Subarray I Problem

LeetCode 643. You are given an integer array nums consisting...

Sliding Window Maximum Problem

LeetCode 239. You are given an array of integersnums, there...

Contains Duplicate III Problem

LeetCode 220. Given an integer array nums and two integers...