Dare2Solve
The problem is to find the maximum average of any subarray of a given length k
in an array. The subarray must be contiguous, and you need to return the maximum possible average value of such subarrays.
The key insight is that by maintaining a sliding window sum of length k
, we can efficiently calculate the sum of each subarray of length k
and then compute the average. By updating this sum as we slide the window across the array, we avoid recalculating the sum from scratch, which improves the efficiency.
k
elements. This will serve as the starting point for our sliding window.O(n)
, where n
is the number of elements in the array. This is because we only pass through the array once.
O(1)
, since we are using only a fixed amount of extra space for variables, regardless of the input size.
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double sum = accumulate(nums.begin(), nums.begin() + k, 0);
double ans = -DBL_MAX;
for (int l = 0, r = l + k - 1; l <= nums.size() - k; l++) {
double avg = sum / k;
ans = max(ans, avg);
sum -= nums[l];
r++;
if (r < nums.size()) {
sum += nums[r];
}
}
return ans;
}
};
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
sum_val = sum(nums[:k])
ans = -float('inf')
for l in range(len(nums) - k + 1):
avg = sum_val / k
ans = max(ans, avg)
if l + k < len(nums):
sum_val -= nums[l]
sum_val += nums[l + k]
return ans
class Solution {
public double findMaxAverage(int[] nums, int k) {
double sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
double ans = -Double.MAX_VALUE;
for (int l = 0, r = l + k - 1; l <= nums.length - k; l++) {
double avg = sum / k;
ans = Math.max(ans, avg);
sum -= nums[l];
r++;
if (r < nums.length) {
sum += nums[r];
}
}
return ans;
}
}
const findMaxAverage = function (x, k) {
let sum = x.slice(0, k).reduce((acc, cur) => acc + cur, 0);
let avg,
ans = -Infinity;
for (let l = 0, r = l + k - 1; l <= x.length - k; l++) {
avg = (sum / k).toFixed(5);
sum -= x[l];
r++;
sum += x[r];
ans = Math.max(ans, avg);
}
return ans;
};