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 public double findMaxAverage(int[] nums, int k) {
3 int sum = 0;
4 for (int i = 0; i < k; i++) {
5 sum += nums[i];
6 }
7 int maxSum = sum;
8 for (int i = k; i < nums.length; i++) {
9 sum = sum - nums[i - k] + nums[i];
10 maxSum = Math.max(maxSum, sum);
11 }
12 return (double) maxSum / k;
13 }
14 public static void main(String[] args) {
15 Solution sol = new Solution();
16 int[] nums = {1, 12, -5, -6, 50, 3};
17 int k = 4;
18 System.out.println(sol.findMaxAverage(nums, k));
19 }
20}In Java, a similar sliding window approach is used. We maintain a running sum of the first k elements. As we slide the window across the array, we adjust the sum by subtracting the element going out of the window and adding the new element. We keep track of the maximum sum encountered.
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)
1using System;
2
public class Solution {
public double FindMaxAverage(int[] nums, int k) {
double maxAvg = -10001.0;
for (int i = 0; i <= nums.Length - k; i++) {
int sum = 0;
for (int j = i; j < i + k; j++) {
sum += nums[j];
}
double avg = (double)sum / k;
if (avg > maxAvg) {
maxAvg = avg;
}
}
return maxAvg;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {1, 12, -5, -6, 50, 3};
int k = 4;
Console.WriteLine(sol.FindMaxAverage(nums, k));
}
}The C# brute force implementation evaluates every possible subarray of k elements to find their sum, computes the average, and checks if it exceeds the maximum average recorded.