सी++ में विभाजित सूची

मान लीजिए कि हमारे पास nums नामक पूर्णांकों की एक सूची है, हमें यह पता लगाना होगा कि क्या हम सूची को दो उप-सूचियों (गैर-रिक्त) में विभाजित कर सकते हैं जैसे कि बाएं भाग में प्रत्येक संख्या सख्ती से कम है दाएँ भाग में प्रत्येक संख्या से अधिक।

इसलिए, यदि इनपुट [6,4,3,8,10] जैसा है, तो आउटपुट सही होगा, जैसा कि बाएँ =[6,4,3] और दाएँ =[8,10]

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

n :=अंकों का आकार
आकार n के दाईं ओर एक सरणी परिभाषित करें
आकार n के बाईं ओर एक सरणी परिभाषित करें
बाएं [0] :=अंक[0]
दाएँ का अंतिम तत्व:=अंकों का अंतिम तत्व
इनिशियलाइज़ करने के लिए मैं :=1, जब i
- बायां [i] :=अधिकतम बायां[i - 1] और अंक[i]
इनिशियलाइज़ करने के लिए i :=n - 2, जब i>=0, अपडेट करें (i से 1 घटाएं), −
करें
- दाएं [i] :=कम से कम दाएं[i + 1] और अंक[i]
इनिशियलाइज़ i :=0 के लिए, जब i
- अगर बाएं [i] <दाएं [i + 1], तो -
  - सही लौटें
झूठी वापसी

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

उदाहरण

#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}