参考文献
ref{:target=”_blank”}
最大上升子序列变种
C++ 代码
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector<int> f(n, 1);
int k = 0; // f[i] 最大的下标
// 转化为最长上升子序列问题
for(int i=0; i<n; ++i){
for(int j=0; j<i; ++j){
if(nums[i]%nums[j]==0){
f[i] = max(f[i], f[j]+1);
if(f[k]<f[i])k = i;
}
}
}
// 逆序寻找结果
vector<int> ret(1, nums[k]);
for(int i=k; i>=0; i--){
if(nums[k]%nums[i] == 0 && f[k] == f[i]+1){
ret.push_back(nums[i]);
// 替换前一个节点
k=i;
}
}
return ret;
}
};