How to implement a sliding window algorithm in C++

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.

Example

We are given an array of size $N$ ; we need to calculate the maximum sum of $K$ consecutive elements.

The most obvious solution would be to find all possible blocks of $K$ elements, and pick the one with the largest sum.

The optimal solution, however, uses the sliding window algorithm. Here is how it works:

Add the first $K$ elements together, and store the sum in the variable currentSum. Since this is the first sum, it is also the current maximum, so store it in variable maximumSum as well.
Since the window size is $K$ , we slide the window one place to the right, and compute the sum of the elements in the window.
If the currentSum is larger than the maximumSum, then update the maximum and repeat step 2. This is illustrated below:

We're given this array of size 6, and need to find 3 consecutive elements which give the maximum sum.

1 of 6

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 maximumSum
  for (int i=k;i<n;i++)
  {
    // Add the rightmost element to the window and
    // discard the leftmost element from the window
    currentSum += 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 left
      end = i; // the window goes upto the position of the newly added element from the right
    } 
  }
  return maximumSum;
}
// driver code
int 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 $N$ 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.

Explanation

In lines 10-16, the first k elements are added together, the sum of this is also the maximum sum yet. The starting and ending positions are also updated.
Lines 18-29 contain the window sliding algorithm, but line 22 is the most important line of code. Here the previous sum, stored in 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.
Lines 25-27 are in charge of updating the maximumSum, if it is smaller than the currentSum, as well as the starting and ending positions of the window where the maximum was found.

How to implement a sliding window algorithm in C++

Example

Implementation

Explanation