Maximum Average Subarray I - Leetcode Solution

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:

1. First, we loop through the array from index 0 to k-1 and calculate the sum of the first k elements.
2. Store this sum value in a variable called max_sum.
3. 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.
4. 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.
5. 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.

1