Solution: Maximum Average Subarray I

Statement

Given an array of integers nums, and an integer k, return the maximum average of a contiguous subarray of length k.

Constraints:

• $1 \leq$k $\leq$ nums.length $\leq$ $10^5$

• $-10^4 \leq$nums[i] $\leq 10^4$

Solution

The algorithm to find the maximum average of a subarray of length k uses the sliding window pattern. First, It calculates the sum of the first k elements of the array and stores them as the current and maximum sum. Then, it slides the window one element at a time over the array. For each new element that enters the window, the algorithm subtracts the element that leaves the window from the current sum and adds the new element to the current sum. This way, the sum of the window elements is calculated without recalculating the entire sum from scratch. The algorithm then updates the maximum sum with the current sum if the value of the current sum is greater than the previously recorded maximum sum. Finally, the algorithm returns the maximum average by dividing the maximum sum with k.

The algorithm to solve this problem is as follows:

• Calculate the sum of the first k elements in nums in current_sum.

• Assign the value of the current_sum to max_sum to keep a record of the maximum sum.

• Loop on nums from index k till nums.length and in each iteration of the loop:

  • Update current_sum by subtracting the element that leaves the window, i.e., nums[i - k], and adding the new element that just entered the window, i.e., nums[i].

  • Check if the value of current_sum is greater than the max_sum; if so, assign the value of current_sum to max_sum.

• After the loop terminates, return the average of the subarray by dividing max_sum with k.

Let’s look at the following illustration to get a better understanding of the solution: