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 In 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.