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; }