Sliding Window Maximum | Dynamic Programming Set 1

Given an array of size n and k, how do you find the maximum for every contiguous subarray of size k?
For example
arr[n] = 1 -2 5 6 0 9 8 -1 2 0

For Window Size, W = 3
Output = 5 6 6 9 9 9 8 2

Algorithm Paradigm: Dynamic Programming

N is number of elements in an array and W is window size . So, Window number = N-W+1
Now divide array into block of W starting from index 1. Here divide into block of size ‘W’=3. For your sample input:

1 -2 5  |  6 0 9  |  8 -1 2  |  0

we will calculate maximum in 2 ways A.) by traversing from left to right B.) by traversing from right to left. but how ??

Firstly, Traversing from Left to Right. For each element a[i] in block we will find maximum till that element a[i] starting from START of Block to END of that block. so Here,

Array 1 -2 5 | 6 0 9 | 8 -1 2 | 0
LR         1 1  5 | 6 6 9 | 8  8  8 | 0

Secondly, Traversing from Right to Left. For each element ‘a[i]’ in block we will find maximum till that element ‘a[i]’ starting from END of Block to START of that block. so Here,

Array 1 -2 5 | 6 0 9 | 8 -1 2 | 0
RL          5 5 5 | 9 9 9 | 8  2  2 | 0

Now we have to do is find maximum for each subarray or window of size ‘W’. so, starting from index = 1 to index = N-W+1 .
max_val[index] = max(RL[index], LR[index+w-1]);

Array : 1 -2 5 | 6 0 9 | 8 -1 2 | 0
LR            1 1 5 | 6 6 9 | 8  8  8 | 0
RL             5 5 5| 9 9 9 | 8  2  2 | 0

for index=1: max_val[1] = max(RL[1],LR[3]) = max(5,5)= 5
Simliarly, for all index i, (i<=(n-k+1)), value at RL[i] and LR[i+w-1] are compared and maximum among those two is answer for that subarray.
So Final Answer : 5 6 6 9 9 9 8 2

Time Complexity: O(n)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int main(){
    int n, w, i, k; // 'n' is number of elements in array
    // 'w' is Window's Size 
    w = 3;
    int arr[] = {1,-2,5,6,0,9,8,-1,2,0}; // Input Array 
    n = sizeof(arr)/sizeof(int);
    k = n - w + 1; // 'K' is number of Windows
    int *LR = new int[n+1]; // maximum from Left to Right
    int *RL = new int[n+1]; // maximum from Right to left
    int *max_val = new int[n+1]; // number of subarrays(windows) will be n-k+1
    	getchar();
    //Generate LeftRight array
    for(i = 1; i <= n; i++) // for maximum Left to Right
	{ 
        if(i % w == 1) // that means START of a block
            LR[i] = arr[i-1];
        else
            LR[i] = max(LR[i - 1], arr[i-1]);        
    }
	
	getchar();
	//Generate RightLeft Array
    for(i = n; i >= 1; i--) // for maximum Right to Left
	{ 
        if(i == n) //If the last block is not of size 'W'. 
            RL[i] = arr[i-1]; 
        else if(i % w == 0) // that means END of a block
            RL[i] = arr[i-1];
        else
            RL[i] = std::max(RL[i+1], arr[i-1]);
    }
 
    for(i = 1; i <= k; i++)    // maximum
        max_val[i] = std::max(RL[i], LR[i + w - 1]);
 
    for(i = 1; i <= k ; i++)
        cout << max_val[i] << " ";
 
    cout << endl;
    //Free allocated memory
    delete [] LR;
    delete [] RL;
    delete [] max_val;
 
    return 0;
}

Site Footer