pythonpython-3.xlogicaveragesub-array

How to get maximum average of subarray?


I have been working this leet code questions

https://leetcode.com/problems/maximum-average-subarray-i/description/

I have been able to create a solution after understanding the sliding window algorithm. I was wondering with my code where my logic is going wrong, I do think my my issue seems to be in this section section of the code, but I am unable to pinpoint why.

        while temp > k:
            temp -= nums[left]
            left += 1 
        ans = temp / (curr - left + 1)

While I do appreciate other solutions and ways solving this problem, I want to understand and get solution working first before I start looking at different ways of doing the problem, this way i get a better understanding of the algorithm.

Full code reference

def findMaxAverage(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: float
    """
    left = 0
    ans = 0
    temp = 0
    
    for curr in range(len(nums)):
        temp += nums[curr]
        curr += 1
        while temp > k:
            temp -= nums[left]
            left += 1 
        ans = temp / (curr - left + 1)
    return ans       

Solution

  • temp is the sum of the subarray, while k is the number of elements in it - you shouldn't be comparing the two, they're two totally different things.

    To implement a sliding window, I'd sum the first k elements of nums, and then run over it where in each iteration I drop the first element and add the last and then check if the sum has increased or not. Once you find the maximum sum, you can find the average by dividing it by k.

    class Solution:
        def findMaxAverage(self, nums: List[int], k: int) -> float:
            currSum = sum(nums[:k])
            maxSum = currSum
            for i in range(k, len(nums)):
                currSum = currSum - nums[i - k] + nums[i]
                maxSum = max(maxSum, currSum)
    
            return maxSum / k