Compute the sum of every contiguous subarray of length k, track the maximum sum, and return the maximum average.
Use a sliding window of size k. Compute the sum of the first k elements, then slide the window by adding the next element and removing the leftmost element. Track the maximum window sum throughout.
""" 0643.1 - Solution 1 - Brute Force Approach """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def findMaxAverage(self, nums: List[int], k: int) -> float:
"""Find Maximum Average Subarray of length k"""
max_sum = float("-inf")
for i in range(len(nums) - k + 1):
current_sum = 0
for j in range(i, i + k):
current_sum += nums[j]
max_sum = max(max_sum, current_sum)
return max_sum / k
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().findMaxAverage([1, 12, -5, -6, 50, 3], 4)) # 12.75
print(Solution().findMaxAverage([5], 1)) # 5.0
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0643.2 - Solution 2 - Sliding Window """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def findMaxAverage(self, nums: List[int], k: int) -> float:
"""Find Maximum Average Subarray of length k"""
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum / k
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().findMaxAverage([1, 12, -5, -6, 50, 3], 4)) # 12.75
print(Solution().findMaxAverage([5], 1)) # 5.0
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()