C++刷leetcode(368. 最大整除子集)【动态规划】
题目描述：给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。
如果有多个目标子集，返回其中任何一个均可。
示例 1:
输入:
输出: (当然, 也正确)
示例 2:
输入:
输出:
vector<int> largestDivisibleSubset(vector<int>& nums) {
vector<int> res;
int len = nums.size();
if(len == 0 )return res;
sort(nums.begin(), nums.end());
vector<int> dp(len, 0);
dp= 1;
for(int i = 1; i < len ; i++){
for(int j = i-1; j>=0; j--){
if(nums % nums == 0){
dp = max(dp, dp+1);
}
}
if(dp == 0) dp = 1;
}//dp记录以nums结尾的最大长度
int max_len = *max_element(dp.begin(), dp.end());
int k = dp.size()-1;
while(k >=0){
if(max_len == 0)break;
if(dp == max_len){
if(res.empty() || res.back()%nums == 0){
res.push_back(nums);
max_len--;
}
}
k--;
}//根据dp返回结果
return res;
}
页:
[1]