643. Maximum Average Subarray I
On This Page
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. The result must be accurate up to a decimal point of 10^(-5).
A straightforward approach would be to calculate the average for every possible subarray of length
k. For each starting point, sum the next
k numbers and determine the average. This will take O(n*k) time which is not efficient for large values of
Hints & Tips
One way to improve the naive solution is by observing the overlapping computations. As we move from one subarray to the next, we are recalculating the sum for mostly the same numbers except for the first and the last numbers. This observation points towards the sliding window technique which can be very efficient for such problems.
We use the sliding window technique. The idea is to maintain a window of size
k and slide it across the array. The sliding window technique is particularly useful in problems where the array input and the window size remain static, but the starting point of the sliding window moves.
- Calculate the sum of the first
- Slide the window by one position at a time. For every slide, subtract the number that is left behind and add the new number that comes into the window. This will give the sum for the next window of
- Keep track of the maximum sum as we slide the window.
def findMaxAverage(nums, k): # Calculate the sum of the first k numbers window_sum = sum(nums[:k]) max_sum = window_sum for i in range(len(nums) - k): window_sum = window_sum - nums[i] + nums[i+k] max_sum = max(max_sum, window_sum) return max_sum / k