C++-এ সর্বোচ্চ বিভাজ্য উপসেট

বিভিন্ন ধনাত্মক পূর্ণসংখ্যার একটি সেট দেওয়া আছে। এমন সবচেয়ে বড় উপসেট খুঁজে বের করতে হবে যাতে এর প্রতিটি জোড়া (Si, Sj) এর জন্য Si % Sj == 0 বা Sj % Si == 0 সত্য হয়।

উদাহরণ: [1,2,3] হলে সম্ভাব্য ফলাফল [1,2] বা [1,3]।

সমাধানের ধাপগুলো:

• ret অ্যারে, endpoint := 0, retLen := 1, n := nums.size()
• যদি n == 0, খালি সেট ফেরত দিন।
• nums সোর্ট করুন।
• আকার n-এর দুটি অ্যারে len আর par, len ১ দিয়ে, par ০ দিয়ে ইনিশিয়ালাইজ করুন।
• i = 1 থেকে n-1 পর্যন্ত:
  • par[i] := i
  • j = 0 থেকে i-1 পর্যন্ত:
    • যদি nums[i] % nums[j] == 0 AND len[j] + 1 > len[i]:
      • len[i] := len[j] + 1
      • par[i] := j
  • যদি len[i] > retLen, retLen := len[i], endpoint := i
• ret-এ nums[endpoint] ঢোকান।
• endpoint != par[endpoint] रहने পর্যন্ত:
  • endpoint := par[endpoint]
  • ret-এ nums[endpoint] ঢোকান
• ret উল্টিয়ে ফেরত দিন।

উদাহরণ (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, ]