Given an array arr[] of size N and an integer K. Find the maximum for each and every contiguous subarray of size K.

Example 1:

```Input:
N = 9, K = 3
a[] = 1 2 3 1 4 5 2 3 6
Output:
3 3 4 5 5 5 6
Explanation:
1st contiguous subarray = {1 2 3} Max = 3
2nd contiguous subarray = {2 3 1} Max = 3
3rd contiguous subarray = {3 1 4} Max = 4
4th contiguous subarray = {1 4 5} Max = 5
5th contiguous subarray = {4 5 2} Max = 5
6th contiguous subarray = {5 2 3} Max = 5
7th contiguous subarray = {2 3 6} Max = 6```

Example 2:

```Input:
N = 10, K = 4
a[] = 8 5 10 7 9 4 15 12 90 13
Output:
10 10 10 15 15 90 90
Explanation:
1st contiguous subarray = {8 5 10 7}, Max = 10
2nd contiguous subarray = {5 10 7 9}, Max = 10
3rd contiguous subarray = {10 7 9 4}, Max = 10
4th contiguous subarray = {7 9 4 15}, Max = 15
5th contiguous subarray = {9 4 15 12},
Max = 15
6th contiguous subarray = {4 15 12 90},
Max = 90
7th contiguous subarray = {15 12 90 13},
Max = 90```

c++ implementation:

```    vector <int> max_of_subarrays(int *a, int n, int k)
{
int i=0; int j=0;

vector<int>v;
deque<int>q;
while(j<n)
{

while(!q.empty() && q.back()<a[j])
q.pop_back();

q.push_back(a[j]);

if(j-i+1==k)
{
v.push_back(q.front());

if(q.front()==a[i])
q.pop_front();

i++;
}

j++;
}
return v;
}```
Time Complexity: O(n)
space Complexity: O(n)

darkmode