Sponsored
Sponsored
The sliding window technique allows us to keep track of the sum of a subarray of fixed length k by adding one new element and removing the first element of the previous window, thus achieving O(n) time complexity.
Time Complexity: O(n)
Space Complexity: O(1)
1class Solution:
2 def findMaxAverage(self, nums, k):
3 current_sum = sum(nums[:k])
4 max_sum = current_sum
5 for i in range(k, len(nums)):
6 current_sum = current_sum - nums[i - k] + nums[i]
7 max_sum = max(max_sum, current_sum)
8 return max_sum / k
9
10sol = Solution()
11nums = [1, 12, -5, -6, 50, 3]
12k = 4
13print(sol.findMaxAverage(nums, k))The Python solution uses list slicing and a simple loop to implement the sliding window technique. It initially calculates the sum of the first k elements. Then it iterates from the kth element to the end of the list, updating the current sum and comparing with the maximum sum found so far, to find the maximum average.
The brute force approach involves checking every possible subarray of length k and calculating its average, then keeping track of the maximum average found. However, this approach is not efficient for large inputs.
Time Complexity: O(n*k)
Space Complexity: O(1)
1#
The C solution calculates the sum and average of every subarray of length k, updating the maximum average found. This implementation is simple but inefficient for large arrays due to its O(n*k) complexity.