C++ এ বিভক্ত তালিকা

ধরুন আমাদের কাছে সংখ্যা বলা পূর্ণসংখ্যার একটি তালিকা আছে, আমাদের খুঁজে বের করতে হবে যে আমরা তালিকাটিকে দুটি সাবলিস্টে (খালি নয়) ভাগ করতে পারি যে বাম অংশের প্রতিটি সংখ্যা কঠোরভাবে কম ডান অংশে প্রতিটি সংখ্যার চেয়ে।

সুতরাং, যদি ইনপুটটি [6,4,3,8,10] এর মত হয়, তাহলে আউটপুটটি সত্য হবে, বাম =[6,4,3] এবং ডান =[8,10]

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

n :=সংখ্যার আকার
n
আকারের একটি অ্যারের ডানদিকে সংজ্ঞায়িত করুন
n
আকারের বাম একটি অ্যারে সংজ্ঞায়িত করুন
বাকি[0] :=সংখ্যা[0]
ডানের শেষ উপাদান :=সংখ্যার শেষ উপাদান
আরম্ভ করার জন্য i :=1, যখন i
- left[i] :=সর্বোচ্চ বাম[i - 1] এবং সংখ্যা[i]
আরম্ভ করার জন্য i :=n - 2, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), −
- ডান [i] :=সর্বনিম্ন অধিকার[i + 1] এবং সংখ্যা[i]
আরম্ভ করার জন্য i :=0, যখন i
- যদি বাম[i]
  - প্রত্যাবর্তন সত্য
মিথ্যা ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool solve(vector<int> &nums) {
      int n = nums.size();
      vector<int> right(n);
      vector<int> left(n);
      left[0] = nums[0];
      right.back() = nums.back();
      for (int i = 1; i < n; i++) {
         left[i] = max(left[i - 1], nums[i]);
      }
      for (int i = n - 2; i >= 0; i--) {
         right[i] = min(right[i + 1], nums[i]);
      }
      for (int i = 0; i < n - 1; i++) {
         if (left[i] < right[i + 1])
         return true;
      }
      return false;
   }
};
main() {
   Solution ob;
   vector<int> v = {6,4,3,8,10};
   cout << (ob.solve(v));
}

ইনপুট

{6,4,3,8,10}