include

include

using namespace std;

void printKMax(int arr[], int n, int k){ deque deq; int i=0; deque::iterator it; for (i = 0; i < k; ++i) { while (!deq.empty() && arr[i] >= arr[deq.back()]) { deq.pop_back(); } deq.push_back(i); } for (; i < n; ++i) { cout << arr[deq.front()] << " "; while (!deq.empty() && deq.front() <= i - k) { deq.pop_front(); } while (!deq.empty() && arr[i] >= arr[deq.back()]) { deq.pop_back(); } deq.push_back(i); } cout << arr[deq.front()] << endl; }

int main(){

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

}

this also exceeded the time limit

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

vector<vector<int>> makesubarray(deque<int> dq, int k) {
    vector<vector<int>> V;
    for (int i = 0; i <= dq.size() - k; i++) { // Change to <= to ensure valid subarray
        vector<int> v;
        for (int j = 0; j < k; j++) {
            v.push_back(dq[i + j]);
        }
        V.push_back(v);
    }
    return V;
}

deque<int> findmax(vector<vector<int>> v) {
    deque<int> dq;
    for (auto &a : v) {
        int max = a[0]; // Initialize max with the first element of the subarray
        for (int i = 1; i < a.size(); i++) { // Start from the second element
            if (a[i] > max) {
                max = a[i]; // Update max if current element is greater
            }
        }
        dq.push_back(max);
    }
    return dq;
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n, k;
        cin >> n >> k;

        deque<int> dq;
        for (int j = 0; j < n; j++) {
            int element;
            cin >> element;
            dq.push_back(element);
        }
        
        for (auto &i : findmax(makesubarray(dq, k))) {
            cout << i << " "; // Add space for better formatting
        }
        cout << endl;
    }
    return 0;
}

`

This is my code which is fine but gives my "exceeded time limits", how can I solve this ?

void printKMax(int arr[], int n, int k){
    deque<deque<int>> d;
    for(int i=0;i<(n-k+1);i++){
        deque<int> temp;
        for(int j=0;j<k;j++){
            temp.push_back(arr[i+j]);
        }
        d.push_back(temp);
    }
    for(deque<int> d1: d){
        auto itr = max_element(d1.begin(), d1.end());
        cout<<*itr<<" ";
    }
    cout<<endl;
}

You need to find the max of the K values. Then while you do not will pop the max value, and not arrive the end of queue, continue comparing to the next value, printing the max and pop_front of queue. If the value to pop is the max value, then start again and find the max of the K values.

This is not optimized and if a lot of max values are repeated the complexity will increment. But this code pass all the tests in time.

void printKMax(int arr[], int n, int k){
	//Write your code here.
    deque<int> fila;
    deque<int>::iterator itr;
    int max = 0;
    
    for (int i = 0; i<n; i++)
    {
        fila.push_back(arr[i]);
    }
    
    while(fila.size() >= k)
    {
        itr = fila.begin();
        for(int i = 0; i<k ; i++)
        {
            if(*itr > max)
                max = *itr;
            itr++;
        }
        cout << max << " ";
        while ((fila.front() != max) && (itr != fila.end()))
        {
            if (max < *itr)
                max = *itr;
            cout << max << " ";
            itr++;
            fila.pop_front();
        }
        fila.pop_front();
        max = 0;
    }
    cout << endl;
}

include

include

using namespace std;

void printKMax(int arr[], int n, int k){ // //Write your code here. // int i = 0; // int j = k-1; // while(jmaxi) maxi = arr[k]; // } // cout< dq;

// Process the first 'k' elements.
for (int i = 0; i < k; i++) {
    // Remove elements smaller than the current one.
    while (!dq.empty() && arr[i] >= arr[dq.back()]) {
        dq.pop_back();
    }
    dq.push_back(i);
}

// Process the remaining elements.
for (int i = k; i < n; i++) {
    // The front of the deque is the largest element of the previous window.
    cout << arr[dq.front()] << " ";

    // Remove elements that are out of this window.
    while (!dq.empty() && dq.front() <= i - k) {
        dq.pop_front();
    }

    // Remove elements smaller than the current one.
    while (!dq.empty() && arr[i] >= arr[dq.back()]) {
        dq.pop_back();
    }

    dq.push_back(i);
}

// Print the maximum of the last window.
cout << arr[dq.front()] << endl;

}

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;

}