Question : You are given an array of integers and a integer k. You need to figure out the maximum of all the subarrays of size k .

Input: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3 
Output: 3 3 4 5 5 5 6
Explanation: 
Maximum of 1, 2, 3 is 3
Maximum of 2, 3, 1 is 3
Maximum of 3, 1, 4 is 4
Maximum of 1, 4, 5 is 5
Maximum of 4, 5, 2 is 5 
Maximum of 5, 2, 3 is 5
Maximum of 2, 3, 6 is 6

Brute Solution :
To get the solution you can simply generate all the subarrays of size k . and find out the maximum of all these subarrays and print it accordingly. Say , you start from the 0th index , now you traverse till (0+k)th index and print the maximum among it . Then you start your next array from 1st index and go till (1+k)th index and print the maxiumum among them and similarly we can continue for all subarrays.
Pseudo Code :
for(i=0 to n-k){
max=arr[i]
for(j=i to i+k-1){
if(a[j]>max){
max=ar[j]
}
}
cout<<max<<“\n”
}
Time Complexity : O(nxk)
Space Complexity : O(1)

Optimal Solution:
To get a better time complexity solution we will be using additional space here . Here we are going to store elements in a decreasing fashion and in order to do so we will be requiring something which is known as deque .It will allow you to push at front also it will allow you to pop back . Now in order to solve this problem , you’ll start iterating at the zeroth index .
Lets take an example array to understand this :

arr[]=[1,3,-1,-3,5,3,6,7], k = 3

Once we start iterating , We can see that our deque doesn’t have anything so in order to maintain the decreasing order you can simply push back this value zero so just push back this value zero which is the index okay now let’s move to thenext which is the index oneso since you have pushed back the value zero that’s nothing but the value one now the moment you come to the index one you have a value three.Now start checking from the back which is theelement at zeroth index of arr and that’s one so now one is lesser than three . We can see that one is lesser than three so we do not require one anymore because we have got three. We’ll take the one out and after this the deque is empty.Now I will plug 3 to back of the deque.

 We will move to the second index so since i’ve moved to the second index we have a minus one now your deque has this first index which is nothing but the value three now as of now we have a minus one now this minus one if i plug into my deque it will maintain a decreasing order and i know if i get a minus 1 it’s not the maximum because 3 will be my maximum so no need to remove anything rather push this index to the back of your deque.Now , here comes the main point , 2 is the last index of the first subarray of size 3 .Since i’m storing in a decreasing order ,if i look from the front whatever value is at the front we can say this is our answer for current subarray .We can get our next window at next index of size 3 from 1st index to 4th index and we continue our above approach .

Code:
C++
Function :

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int>dq;
vector<int>ans;
for (int i=0; i<nums.size(); i++) {
if (!dq.empty() && dq.front() == i-k) dq.pop_front();

        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();

        dq.push_back(i);
        if (i>=k-1) ans.push_back(nums[dq.front()]);
    }
    return ans;
}

Time Complexity : O(n)
Space Complexity : O(1)