C++で最大の分割可能なサブセット

明確な正の整数のセットがあるとすると、このサブセット内の要素の（Si、Sj）のようなすべてのペアがSi mod Sj=0またはSjmodSi=0を満たすような最大のサブセットを見つける必要があります。

したがって、入力が[1,2,3]のような場合、可能な結果は[1,2]または[1,3]

これを解決するには、次の手順に従います-

• 配列retを作成し、endpoint：=0、retLen：=1、n：=numsのサイズを設定します

• nが0の場合、空のセットを返します

• nums配列を並べ替える

• サイズnの2つの配列lenとparを作成し、lenを1で初期化し、parを0で初期化します

• 1からn–1の範囲のiの場合

  • par [i]：=i

  • 0からi–1の範囲のjの場合

    • nums [i] mod nums [j]=0かつlen[j]+ 1> len [i]の場合、

      • len [i]：=len [j] + 1

      • par [i]：=j

  • len [j]> retLenの場合、retLen：=len [i]およびendpoint：=i

• nums[endPoint]をretに挿入します

• エンドポイントはpar[endPoint]

  と同じではありませんが

  • エンドポイント：=par [endPoint]

  • nums[endPoint]をretに挿入します

• リストを逆にして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, ]