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