How to get maximum average of subarray?

Question

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

Why are you comparing temp with k? They are completely unrelated. temp is the ongoing sum of values from the array, and k is merely a count of how many values to use. Comparing them to each other makes no sense. It's like comparing a person's height to the temperature outside. — Tom Karzes
– Tom Karzes, Commented Jan 5 at 8:48
Including the link is good, but don't rely on it. All necessary information must be included in the question. That includes a description of what the code is supposed to do, an example, and telling us why you think "my logic is going wrong" (presumably you have an input case where you compute a wrong output?). — no comment
– no comment, Commented Jan 5 at 12:02

Mureinik · Accepted Answer · 2025-01-05 10:11:36Z

1

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

answered Jan 5 at 10:11

Mureinik

316k54 gold badges401 silver badges405 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Zubair Amjad Jan 6 at 4:02

Awesome! I just wanna understand this line a bit more currSum = currSum - nums[i - k] so i-k is the index where we drop the first element of the subarray?

Mureinik Jan 6 at 9:34

@ZubairAmjad exactly - currSum strats out as the first subarray. Then, in each iteration of the loop we drop the first element of the subarray and add the following one.

jackal · Accepted Answer · 2025-01-05 10:41:31Z

0

The value of k is the size of the sliding window. deque (from collections) is a very efficient way to maintain the window.

Take the initial subsequence, construct a deque from that list and note its sum. Then you can iterate over the input list starting from k. Keep a note of the latest sum and adjust it by adding in each new value and subtracting the leftmost value from the deque.

Then it's just:

from collections import deque

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        ss = nums[:k]
        d = deque(ss)
        sd = cs = sum(ss)
        for n in nums[k:]:
            sd = sd - d.popleft() + n
            if sd > cs:
                cs = sd
            d.append(n)
        return cs / k

edited Jan 5 at 10:41

answered Jan 5 at 10:28

jackal

29.1k3 gold badges10 silver badges28 bronze badges

Collectives™ on Stack Overflow

How to get maximum average of subarray?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related