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)
1#include <stdio.h>
2
3float findMaxAverage(int* nums, int numsSize, int k) {
4 int sum = 0;
5 for (int i = 0; i < k; i++) {
6 sum += nums[i];
7 }
8 int maxSum = sum;
9 for (int i = k; i < numsSize; i++) {
10 sum = sum - nums[i - k] + nums[i];
11 if (sum > maxSum) {
12 maxSum = sum;
13 }
14 }
15 return (float)maxSum / k;
16}
17
18int main() {
19 int nums[] = {1,12,-5,-6,50,3};
20 int k = 4;
21 printf("%f\n", findMaxAverage(nums, 6, k));
22 return 0;
23}The C code initializes a sum of the first k elements and iterates over the elements from k to the end of the array. It updates the sum to add the current element and subtract the element that is sliding out of the window, then updates maxSum if the new sum is greater. Finally, it returns 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)
1class SolutionIn Java, the brute force method calculates the sum for each subarray of length k and tracks the maximum average obtained, which is inefficient for large arrays.