C++ deque STL - Maximum of contiguous subarray

Question

This is a hakerrank question Given a set of arrays of size and an integer , you have to find the maximum integer for each and every contiguous subarray of size for each of the given arrays.

Input Format

First line of input will contain the number of test cases T. For each test case, you will be given the size of array N and the size of subarray to be used K. This will be followed by the elements of the array Ai.

Output Format

For each of the contiguous subarrays of size of each array, you have to print the maximum integer.

Sample Input

2
5 2
3 4 6 3 4
7 4
3 4 5 8 1 4 10
Sample Output

4 6 6 4
8 8 8 10
Explanation

For the first case, the contiguous subarrays of size 2 are {3,4},{4,6},{6,3} and {3,4}. The 4 maximum elements of subarray of size 2 are: 4 6 6 4.

For the second case,the contiguous subarrays of size 4 are {3,4,5,8},{4,5,8,1},{5,8,1,4} and {8,1,4,10}. The 4 maximum element of subarray of size 4 are: 8 8 8 10.

Brute force method works fine. But it needs optimized code. I read many methods to implement. The algorithm given on geeksforgeeks works on test cases, but I am unable to comprehend the logic. One algorithm I understood and implemented as follows. But, this doesn't work on real test cases. Althouhg giving correct results on custom input and sample input. Can anyone correct me or explain any other algorithm for this problem? Please help.

#include <iostream>
#include <deque> 
using namespace std;

void printKMax(int arr[], int n, int k){
    deque<int> dq;
    //For each subarray
    //Index of max element stored at the end of deque
    for(int i=0; i<n-k+1; i++){
        //This will run only once
       if(dq.empty()){
           dq.push_back(0);
           for(int j=1; j<=k-1; j++){
               if(arr[j] > arr[i]){
                    dq.push_back(j);
               }else{
                   dq.push_front(j);
               }
           }
           cout<<arr[dq.back()]<<" ";
       }
       else{
           //Check if max index is still under current window
           if(dq.back() < i){
               dq.pop_back();
               int maxIndex=i+k-1;
               for(int j=0; j<dq.size(); j++){
                   if(arr[dq[j]] > arr[maxIndex]){
                       int temp= maxIndex;
                       maxIndex = dq[j];
                       dq[j] = temp;
                   }
               }
               dq.push_back(maxIndex);
               
           cout<<arr[dq.back()]<<" ";
           }
           else{
               //Check if new index is larger than the max of current window
               dq.pop_front();
                if(arr[dq.back()] > arr[i+k-1])
                    dq.push_front(i+k-1);
                else {
                    dq.push_back(i+k-1);
                }
                
           cout<<arr[dq.back()]<<" ";
           }
       }
    }
    cout<<"\n";
}

int main(){
  
    int t;
    cin >> t;
    while(t>0) {
        int n,k;
        cin >> n >> k;
        int i;
        int arr[n];
        for(i=0;i<n;i++)
            cin >> arr[i];
        printKMax(arr, n, k);
        t--;
    }
    return 0;
}

Answer 1

#include <iostream>
#include <deque> 
using namespace std;

void printKMax(int arr[], int n, int k)
{
    //Write your code here.
    /* Deque-STL in C++ - Hacker Rank Solution START */
    deque<int> Qi(k);
    int i;
    for (i = 0; i < k; i++) 
    {
        while ((!Qi.empty()) && (arr[i] >= arr[Qi.back()]))
            Qi.pop_back();
        Qi.push_back(i);
    }
    for ( ; i < n; i++) {
        cout << arr[Qi.front()] << " ";
        while ((!Qi.empty()) && (Qi.front() <= i - k))
            Qi.pop_front();
        while ((!Qi.empty()) && (arr[i] >= arr[Qi.back()]))
            Qi.pop_back();
        Qi.push_back(i);
    }
    cout << arr[Qi.front()] << endl;
    /* Deque-STL in C++ - Hacker Rank Solution END */
}

int main()
{
  
    int t;
    cin >> t;
    while(t>0) 
    {
        int n,k;
        cin >> n >> k;
        int i;
        int arr[n];
        for(i=0;i<n;i++)
            cin >> arr[i];
        printKMax(arr, n, k);
        t--;
    }
    return 0;
}