## Similar Problems

Similar Problems not available

# Maximum Average Subarray I - Leetcode Solution

## Companies:

LeetCode: Maximum Average Subarray I Leetcode Solution

Difficulty: Easy

Topics: sliding-window array

Problem Statement:

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example:

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

Approach:

- First, we loop through the array from index 0 to k-1 and calculate the sum of the first k elements.
- Store this sum value in a variable called max_sum.
- Then we loop through the rest of the array starting from index k and calculate the sum of the next k elements. Subtract the value of the first element of the previous k-length subarray from this sum and add the next element in the current index to get the sum of the current k-length subarray.
- Calculate the average of the current k-length subarray, and if it is greater than the previous maximum average, store this value in the max_sum variable.
- Return the max_sum variable divided by k to get the maximum average.

Code:

def findMaxAverage(nums, k): # Calculate initial sum of first k elements max_sum = sum(nums[:k])

```
# Loop through the rest of the array
for i in range(k, len(nums)):
# Calculate sum of current k-length subarray
current_sum = sum(nums[i-k+1:i+1])
# If current sum is greater than previous maximum sum, update max_sum
if current_sum > max_sum:
max_sum = current_sum
# Return maximum average
return max_sum/k
```

Time Complexity:

The time complexity of this algorithm is O(n), where n is the length of the input array. We only loop through the array once, so the time complexity is linear.

Space Complexity:

The space complexity of this algorithm is O(1), as we are not using any extra data structures to store information. We are only using a few variables to keep track of the maximum sum and the current sum.

## Maximum Average Subarray I Solution Code

`1`