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)
1function findMaxAverage(nums, k) {
2 let sum = 0;
3 for (let i = 0; i < k; i++) {
4 sum += nums[i];
5 }
6 let maxSum = sum;
7 for (let i = k; i < nums.length; i++) {
8 sum = sum - nums[i - k] + nums[i];
9 maxSum = Math.max(maxSum, sum);
10 }
11 return maxSum / k;
12}
13
14const nums = [1, 12, -5, -6, 50, 3];
15const k = 4;
16console.log(findMaxAverage(nums, k));The JavaScript solution also employs a sliding window technique, where it keeps a sum of the first k elements, and as the loop progresses, it subtracts the element that goes out of the window and adds the new element entering the window. It updates and tracks the maximum sum found so far to determine the result.
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#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double maxAvg = -10001;
for (int i = 0; i <= nums.size() - k; ++i) {
int sum = 0;
for (int j = i; j < i + k; ++j) {
sum += nums[j];
}
double avg = static_cast<double>(sum) / k;
if (avg > maxAvg) {
maxAvg = avg;
}
}
return maxAvg;
}
};
int main() {
Solution sol;
vector<int> nums = {1, 12, -5, -6, 50, 3};
int k = 4;
cout << sol.findMaxAverage(nums, k) << endl;
return 0;
}The C++ solution applies a similar brute force strategy, iteratively calculating the sum and average for each possible subarray of length k, and compares it to the maximum average seen.