C++ में सबसे बड़ा विभाज्य उपसमुच्चय

मान लीजिए कि हमारे पास अलग-अलग सकारात्मक पूर्णांकों का एक सेट है, हमें सबसे बड़ा उपसमुच्चय ढूंढना है, जैसे कि इस उपसमुच्चय में तत्वों का प्रत्येक जोड़ा (Si, Sj) संतुष्ट करता है:Si mod Sj =0 या Sj mod Si =0।

इसलिए यदि इनपुट [1,2,3] जैसा है, तो संभावित परिणाम [1,2] या [1,3]

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

• एक सरणी रिट बनाएं, एंडपॉइंट सेट करें:=0, रेटलेन:=1, एन:=अंकों का आकार

• अगर n 0 है, तो खाली सेट लौटाएं

• क्रमांक संख्या सरणी

• दो सरणियाँ बनाएं लेन और आकार n के बराबर, लेन को 1 से प्रारंभ करें, और 0 के साथ बराबर करें

• मैं के लिए 1 से n - 1 की सीमा में

  • पार[i] :=मैं

  • j के लिए 0 से i - 1 की सीमा में

    • यदि अंक [i] आधुनिक अंक [j] =0 और लेन [j] + 1> लेन [i], तो

      • लेन[i] :=लेन[j] + 1

      • पार[i] :=j

  • अगर लेन [j]> रिटलेन, फिर रेटलेन:=लेन [i] और एंडपॉइंट:=i

• nums[endPoint] को रिट में डालें

• जबकि एंडपॉइंट समान नहीं है par[endPoint]

  • समापन बिंदु:=बराबर [अंत बिंदु]

  • nums[endPoint] को रिट में डालें

• सूची को उलट दें और वापस लौटें

उदाहरण(C++)

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> largestDivisibleSubset(vector<int>& nums) {
      vector <int> ret;
      int endPoint = 0;
      int retLen = 1;
      int n = nums.size();
      if(!n) return {};
      sort(nums.begin(), nums.end());
      vector <int> len(n, 1);
      vector <int> par(n, 0);
      for(int i = 1; i < n; i++){
         par[i] = i;
         for(int j = 0; j < i; j++){
            if(nums[i] % nums[j] == 0 && len[j] + 1 > len[i]){
               len[i] = len[j] + 1;
               par[i] = j;
            }
         }
         if(len[i] > retLen){
            retLen = len[i];
            endPoint = i;
         }
      }
      ret.push_back(nums[endPoint]);
      while(endPoint != par[endPoint]){
         endPoint = par[endPoint];
         ret.push_back(nums[endPoint]);
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3};
   print_vector(ob.largestDivisibleSubset(v));
}

इनपुट

[1,2,3]

आउटपुट

[1, 2, ]