---
tags: data_structure_python
---

# Maximum Average Subarray I

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 1:**

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``

**Note:**

- 1 <= k <= n <= 30,000.
- Elements of the given array will be in the range [-10,000, 10,000].

# Solution

## Solution 1: Sliding window

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        beg, end, maxi = 0, 0, float("-inf")
        curr_maxi = 0
        
        while end < len(nums):
            curr_maxi += nums[end]
            end += 1
        
            if (end - beg) == k:
                maxi = max(curr_maxi, maxi)
                curr_maxi -= nums[beg]
                beg += 1
        
        return maxi / k

### Solution 2: Sliding window

Following the template this time.

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # Time complexity: O(n).
        # Space complexity: O(1).
        m, beg, end = len(nums), 0, 0
        maxi = -float("inf")
        window = 0

        while end < m:
            
            window += nums[end]
            
            if end-beg+1 > k:
                window -= nums[beg]
                beg += 1
            if end-beg+1 == k: 
                maxi = max(maxi, window)
                
            end += 1
    
        return maxi/k