C ++中最大的可分割子集
假设我们有一组不同的正整数，我们必须找到最大子集，以使该子集中的每对像(Si,Sj)的元素都满足：SimodSj=0或SjmodSi=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]modnums[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, ]