LeetCode Challenge #643. Maximum Average Subarray I

Question 14 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #643. Maximum Average Subarray I

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:

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

Constraints:

n == nums.length
1 <= k <= n <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Video Solution

C++ Solution

				
					class Solution {
public:

double findMaxAverage(vector&lt;int&gt;&amp; nums, int k) {

    int curr=0;
    
    for(int i=0; i&lt;k; i++)
    {
        curr+=nums[i];
    }

    int maxx=curr;
    
    for(int i=k; i&lt;nums.size(); i++)
    {
        curr+=nums[i]-nums[i-k];
        maxx=max(maxx,curr);
    }
    
    return (double)maxx/k;

    }  
};

Code Explanation

In this program, we have to find a type of contiguous array whose length is k, which has the maximum possible value.

Let’s see the approach towards the code:

1. First, we initialise a variable ‘curr’ to store the sum of the current subarray.

2. Now we will use ‘for’ loop for calculating the sum of the first ‘k’ terms

• Also, for storing the maximum sum that we have obtained till now, we use ‘maxx=curr’ for storing the sum till now.

3. Then we have used a second loop that starts from position ‘k’ and goes up to the end of the array. (This is for the other half array.)

• Now inside the loop, the value of ‘curr’ current is updated by adding the current element at position ‘i’ and subtracting the element at position ‘i-k’.

4. Also, we will update the value of ‘maxx’ like, if the value that has been found is maximum, then no problem, but if the maximum value is not known yet and the ‘current’ value is greater, update ‘maxx’. So that ‘maxx’ will store all the maximum values.

5. Now, we need to return the typecasted value and divide ‘maxx’ by ‘k’ to find the maximum average.

Question 14 of 75 - LeetCode Weekly Challenge