368、最大整除子集
给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。
如果有多个目标子集，返回其中任何一个均可。
示例 1:
输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)
示例 2:
输入: [1,2,4,8]
输出: [1,2,4,8]
题解
1、动态规划
- 当
nums[i] % nums[j] == 0 && dp[i] <= dp[j]时，有：
$dp[i] = max(dp[i],dp[j]), 0<= j < i$
- 代码
// java
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
// 最大长度max 及其 下标end
int max = 0, end = -1;
int[] dp = new int[len];
Arrays.fill(dp,1);
int[] last = new int[len];
Arrays.fill(last,-1);
List<Integer> res = new ArrayList<>();
for (int i = 0;i < len;i++ ){
for (int j = 0;j < i;j++) {
// nums对于之前的所有元素，进行判断，更新为最长的整除子集
// 因为已经排过序，所以只需要判断后面的除以前面的
if (nums[i] % nums[j] == 0 && dp[i] <= dp[j]) {
dp[i] = dp[j] + 1;
last[i] = j;
}
}
if (dp[i] > max) {
max = dp[i];
end = i;
}
}
// 如果求最大长度，直接返回 max
// 回顾遍历，集成结果集合
for (int i = end;i != -1;i = last[i]) {
res.add(nums[i]);
}
return res;
}
}
- C++
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
int sz = nums.size(),mx = 0,end = -1;
// dp状态数组 last最长序列在源数组的下标 res结果集合
vector<int> dp(sz,1),last(sz,-1),res;
sort(nums.begin(),nums.end());
for(int i = 0;i<sz;i++){
// 逐渐变长
for(int j = 0;j<i;j++){
// nums对于之前的所有元素，进行判断，更新为最长的整除子集
if(nums[i] % nums[j] == 0 && dp[i] <= dp[j]){
dp[i] = dp[j]+1;
last[i] = j;
}
}
if(dp[i]>mx){
mx = dp[i];
end = i;
}
}
for(int i = end;i!=-1;i = last[i]){//倒序输出
res.push_back(nums[i]);
}
return res;
}
};
// 作者：leolee
// 链接：https://leetcode-cn.com/problems/largest-divisible-subset/solution/ge-ren-ti-jie-dpcon2-by-leolee/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
