Sliding Window Maximum – C++ Implementation

This C++ program finds the maximum value in each sliding window of size k in a given array using an efficient method.

#include
#include
#include

/**
* Prints maximum of every subarray of size k.
* @param arr The input array.
* @param n The size of the input array.
* @param k The size of the sliding window.
*/
void printMax(int arr[], int n, int k) {
// Create a Double Ended Queue, Qi that will store indexes of array elements
// The queue will store indexes of useful elements in every window and it will
// maintain decreasing order of values from front to rear in Qi, i.e.,
// arr[Qi.front()] to arr[Qi.rear()] are sorted in decreasing order
std::deque Qi(k);

// Process first k (or first window) elements of array
int i;
for (i = 0; i < k; ++i) { // For every element, the previous smaller elements are useless so // remove them from Qi while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back(); // Remove from rear

// Add new element at rear of queue
Qi.push_back(i);
}

// Process rest of the elements, i.e., from arr[k] to arr[n-1]
for (; i < n; ++i) {
// The element at the front of the queue is the largest element of
// previous window, so print it
std::cout << arr[Qi.front()] << ” “;

// Remove the elements which are out of this window
while ((!Qi.empty()) && Qi.front() <= i – k) Qi.pop_front(); // Remove from front of queue // Remove all elements smaller than the currently // being added element (remove useless elements) while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back();

// Add current element at the rear of Qi
Qi.push_back(i);
}

// Print the maximum element of last window
std::cout << arr[Qi.front()] << std::endl;
}

int main() {
int arr[] = {12, 1, 78, 90, 57, 89, 56};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
printMax(arr, n, k);
return 0;
}

Function Documentation

void printMax(int arr[], int n, int k)

This function prints the maximum of every subarray of size k.

• Parameters:
  • arr[]: The array of integers.
  • n: The number of elements in the array.
  • k: The size of the sliding window.
• Returns: None. The function directly prints the maximum of each window in the console.
• Description:The function uses a deque to store the indices of array elements. It ensures that the deque always has indices in decreasing order of their corresponding values in the array. This way, the maximum of any window is always at the front of the deque.It first processes the initial window of size k, removing indices of all elements smaller than the current element (since they cannot be the maximum). Then, for each subsequent element, it prints the maximum of the current window, removes indices of elements not part of the window, and continues to maintain the decreasing order property in the deque.

Sample Usage

        int arr[] = {12, 1, 78, 90, 57, 89, 56};
        int n = sizeof(arr) / sizeof(arr[0]);
        int k = 3;
        printMax(arr, n, k);

This will output: 78 90 90 89