The sliding window algorithm can be used to solve problems that involve linear sequences, such as arrays. A window is a contiguous sequence which is part of an array. As the name suggests, the window is slid over the array. Some operations are performed on elements within this window, and then the window is slid further.
Let’s look at an example problem to make things clearer.
We are given an array of size ; we need to calculate the maximum sum of consecutive elements.
The most obvious solution would be to find all possible blocks of elements, and pick the one with the largest sum.
The optimal solution, however, uses the sliding window algorithm. Here is how it works:
currentSum
. Since this is the first sum, it is also the current maximum, so store it in variable maximumSum
as well.currentSum
is larger than the maximumSum
, then update the maximum and repeat step 2.
This is illustrated below:This is how it is implemented in C++:
int maxSum(int arr[], int k, int n, int &start, int &end){if (k > n){return -1;}int maximumSum = 0;int currentSum = 0;// Compute the initial sum of first K elements.for (int i=0;i<k;i++){currentSum += arr[i];}maximumSum = currentSum;start = 0;end = k - 1;// Sliding the window and updating maximumSumfor (int i=k;i<n;i++){// Add the rightmost element to the window and// discard the leftmost element from the windowcurrentSum += arr[i] - arr[i-k];if (currentSum > maximumSum){maximumSum = currentSum;start = i - k + 1; // the window starts one ahead of the element that was removed from the leftend = i; // the window goes upto the position of the newly added element from the right}}return maximumSum;}// driver codeint main(){int start = 0;int end = 0;int arr[] = {6, 2, -1, 9, 1, -2};int k = 3;int n = (sizeof(arr)/sizeof(*arr));int maxsum = maxSum(arr, k, n, start, end);cout << "The maximum sum is " << maxsum;cout << " from position " << start << " till " << end << endl;return 0;}
The function maxSum()
is called with the following parameters:
arr[]
, which is the array of integers.k
, which is the window size, and n
, which is the size of array arr
.start
and end
will store the starting and ending indexes of the window with the maximum sum. These are initially passed as 0.k
elements are added together, the sum of this is also the maximum sum yet. The starting and ending positions are also updated.currentSum
, is used to calculate the new current sum. This new current sum is found by adding the window’s new element and removing the old one.maximumSum
, if it is smaller than the currentSum
, as well as the starting and ending positions of the window where the maximum was found.Free Resources