C++ প্রোগ্রাম প্রতিটি k আকারের সংলগ্ন সাবয়ারের সর্বাধিক সন্ধান করতে

ধরুন আমাদের n উপাদান সহ একটি অ্যারে এবং একটি মান k আছে। k.

সুতরাং, যদি ইনপুটটি arr =[3,4,6,2,8], k =3 এর মত হয়, তাহলে আউটপুট হবে 3 আকারের সংলগ্ন সাবয়ারেগুলি হল [3,4,6], [4,6, 2], [6,2,8], তাই সর্বাধিক উপাদান হল 6, 6 এবং 8৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• কি আকারের একটি deque Qi সংজ্ঞায়িত করুন
• আরম্ভ করার জন্য i :=0, যখন i
• যখন Qi খালি না থাকে এবং arr[i]>=arr[Qi-এর শেষ উপাদান], কর:
  • কিউই থেকে শেষ উপাদান মুছুন
• Qi-এর শেষে 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