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)
1using System;
2
3public class Solution {
4 public double FindMaxAverage(int[] nums, int k) {
5 int sum = 0;
6 for (int i = 0; i < k; i++) {
7 sum += nums[i];
8 }
9 int maxSum = sum;
10 for (int i = k; i < nums.Length; i++) {
11 sum = sum - nums[i - k] + nums[i];
12 maxSum = Math.Max(maxSum, sum);
13 }
14 return (double) maxSum / k;
15 }
16 public static void Main(string[] args) {
17 Solution sol = new Solution();
18 int[] nums = {1, 12, -5, -6, 50, 3};
19 int k = 4;
20 Console.WriteLine(sol.FindMaxAverage(nums, k));
21 }
22}The C# code maintains a running sum of the first k elements, then iterates over the array to update the sum as the window slides. It updates the maximum sum encountered and returns the average as a double.
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)
1function
The JavaScript brute force solution focuses on iterating through each possible subarray of k length, calculating the average, and identifying the maximum average value. It iteratively sums up values for each subarray but can be slow for large arrays due to the double loop structure.