[LeetCode] 643. Maximum Average Subarray I

1. Question

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

Input: nums = [5], k = 1
Output: 5.00000

2. Thoughts

ex) nums =1 2 3 4 5, k = 3

First I've thought of naively adding all k elements and finding the max then
ex) max(123, 234,345)

Yet, I've realized that adding elements are being done multiple times, thus I came up with:

1. Iterate through (k,len(nums))
2. first add the first k elements
3. then minus that sub array's first element, and add the last element of the new sub array
4. recursively find the largest max sub array

3. Tips learned

How to represent Infinity

1. Using float('inf') and float('-inf)

positive_infinity = float('inf') 
negative_infinity = float('-inf')

2. Using Python’s math module

import math
 
positive_infinity = math.inf 
negative_infinity = -math.inf 

3. Integer maxsize

import sys

maxSize = sys.maxsize 
minSize = -sys.maxsize 

4. Using Python’s decimal module

from decimal import Decimal
 
positive_infinity = Decimal('Infinity') 
negative_infinity = Decimal('-Infinity') 

5. Using Numpy Library

from numpy import inf

positive_infinity = inf 
negative_infinity = -inf 

4. My solution

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
         maxs = avgSum = sum(nums[0:k])
        for i in range(k, len(nums)):
            avgSum = avgSum + nums[i] - nums[i - k]
            maxs = max(maxs, avgSum)

        return maxs / k

127/127 cases passed (991 ms)
Your runtime beats 91.77 % of python3 submissions
Your memory usage beats 47.2 % of python3 submissions (28 MB)

5. AI Solution and Improvements

Certainly! Your current solution is already quite efficient as it uses a sliding window approach to keep track of the sum of the current subarray of size k, achieving O(n) time complexity. However, we can make some minor adjustments to make the code more "Pythonic" and clear:

1. Rename the variables to follow more conventional naming (e.g., max_avg instead of maxs).
2. Provide meaningful comments to explain what's happening at each step.

Here's a slightly revised version:

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # Start with the sum of the first k elements
        current_sum = sum(nums[:k])
        max_avg = current_sum

        # Iterate through the rest of the elements, updating the current_sum by adding the next element
        # and subtracting the first element of the previous subarray
        for i in range(k, len(nums)):
            current_sum = current_sum + nums[i] - nums[i - k]
            max_avg = max(max_avg, current_sum)

        # Divide the max sum by k to get the maximum average
        return max_avg / k

I've kept the core logic of your original code since it is already an efficient approach to solving the problem. The changes are primarily related to making the code more readable and expressive.