Sliding Window Technique
Learn about sliding window technique
Introduction
Suppose we are given an array and a number . We want to find a subarray of length with the maximum average value.
Learn about sliding window technique
Suppose we are given an array and a number . We want to find a subarray of length with the maximum average value.
Since all subarrays must have the same length, this is equivalent to finding the subarray of length with the maximum sum.
A simple solution is to check every subarray of length and compute its average independently.
This works in time, because for each starting position we recompute the whole sum from scratch.
We can do better.
Instead of recalculating the sum for every subarray, we keep the sum of the current segment of length and update it when the segment moves one step to the right.
We call the current segment a window.
If we already know the sum of the current window, then after shifting it one step to the right:
So the new sum can be updated in constant time.
First, compute the sum of the first window .
Then, for each next position, move the window one step to the right:
In other words, when moving to the window ending at position , the sum changes by:
The average of the current window is simply:
Let
The windows are:
So the maximum average is obtained from the subarray .
for (int i = 1; i + k - 1 <= n; i++) {
double sum = 0;
for (int j = 0; j < k; j++) {
sum += a[i + j];
}
sum /= k;
res = max(res, sum);
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<double> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
double sum = 0;
for (int i = 1; i <= k; i++) {
sum += a[i];
}
double res = sum / k;
for (int i = k + 1; i <= n; i++) {
sum += a[i] - a[i - k];
res = max(res, sum / k);
}
cout << fixed << setprecision(10) << res << "\n";
return 0;
}