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 <iostream>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 double findMaxAverage(vector<int>& nums, int k) {
8 int sum = 0;
9 for (int i = 0; i < k; ++i) {
10 sum += nums[i];
11 }
12 int maxSum = sum;
13 for (int i = k; i < nums.size(); ++i) {
14 sum = sum - nums[i - k] + nums[i];
15 maxSum = max(maxSum, sum);
16 }
17 return static_cast<double>(maxSum) / k;
18 }
19};
20
21int main() {
22 Solution sol;
23 vector<int> nums = {1, 12, -5, -6, 50, 3};
24 int k = 4;
25 cout << sol.findMaxAverage(nums, k) << endl;
26 return 0;
27}In C++, the solution is encapsulated in a class method. It works similarly to the C solution, using vector operations and keeping a running sum by sliding over the array while updating the maximum sum found.
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
The Python brute force solution exhaustively checks all possible subarrays of length k, calculating the sum and average for each to find the maximum average. This approach is computationally expensive for higher values of n.