C ++中最大的可分割子集

假设我们有一组不同的正整数，我们必须找到最大子集，以使该子集中的每对像(Si,Sj)的元素都满足：Si mod Sj = 0或Sj mod Si = 0。

因此，如果输入像[1,2,3]，则可能的结果可能像[1,2]或[1,3]

为了解决这个问题，我们将遵循以下步骤-

• 创建一个数组ret，设置端点：= 0，retLen：= 1，n：= nums的大小

• 如果n为0，则返回空集

• 排序nums数组

• 创建大小为n的两个数组len和par，用1初始化len，用0初始化par

• 当我在1到n – 1的范围内时

• 如果nums [i] mod nums [j] = 0且len [j] + 1> len [i]，则

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

• par [i]：= j

• par [i]：= i

• 对于0到i – 1范围内的j

• 如果len [j]> retLen，则retLen：= len [i]和端点：= i

• 将nums [endPoint]插入ret

• 而端点与par [endPoint]不同

• 端点：= par [endPoint]

• 将nums [endPoint]插入ret

• 反转列表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, ]