प्रत्येक k आकार के सन्निहित उप-सरणी का अधिकतम पता लगाने के लिए C++ प्रोग्राम

मान लीजिए कि हमारे पास n तत्वों और एक मान k के साथ एक सरणी है। हमें k आकार के प्रत्येक सन्निहित उप-सरणी के लिए अधिकतम मान ज्ञात करना होगा।

इसलिए, यदि इनपुट arr =[3,4,6,2,8], k =3 जैसा है, तो आउटपुट आकार 3 के सन्निहित उप-सरणी होंगे [3,4,6], [4,6, 2], [6,2,8], इसलिए अधिकतम तत्व 6, 6 और 8 हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• क आकार k का एक deque Qi परिभाषित करें
• इनिशियलाइज़ i :=0 के लिए, जब i
• जबकि क्यूई खाली नहीं है और गिरफ्तारी[i]>=arr[क्यूई का अंतिम तत्व], करें:
  • क्यूई से अंतिम तत्व हटाएं
• क्यूई के अंत में i डालें

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int main(){
   vector<int> arr = {3,4,6,2,8};
   int k = 3;
   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 < arr.size(); ++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;
}

इनपुट

{3,4,6,2,8}, 3

आउटपुट

6 6 8