LeetCode （7）最大整除子集 （中等）

题目描述：

给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
answer[i] % answer[j] == 0 ，或
answer[j] % answer[i] == 0
如果存在多个有效解子集，返回其中任何一个均可。

代码：

class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int[] f = new int[n];
int[] g = new int[n];
for (int i = 0; i < n; i++) {
// 至少包含自身一个数，因此起始长度为 1，由自身转移而来
int len = 1, prev = i;
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0) {
// 如果能接在更长的序列后面，则更新「最大长度」&「从何转移而来」
if (f[j] + 1 > len) {
len = f[j] + 1;
prev = j;
}
}
}
// 记录「最终长度」&「从何转移而来」
f[i] = len;
g[i] = prev;
}

// 遍历所有的 f[i]，取得「最大长度」和「对应下标」
int max = -1, idx = -1;
for (int i = 0; i < n; i++) {
if (f[i] > max) {
idx = i;
max = f[i];
}
}

// 使用 g[] 数组回溯出具体方案
List<Integer> ans = new ArrayList<>();
while (ans.size() != max) {
ans.add(nums[idx]);
idx = g[idx];
}
return ans;
}
}

作者：AC_OIer
链接：https://leetcode-cn.com/problems/largest-divisible-subset/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-0a3jc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

值得注意的是：

这个题目可以用dp方法求解，解题之前先得明白倍数关系

如果当前的元素与之前的最长整除子集最后一个元素呈倍数关系，那么它与之前的元素也一定成倍数关系

当然所有dp方法的通病也在，这可能得不到最优解。因为dp只求局部最优，和整体最优解还有一定的差距。

LeetCode （7）最大整除子集 （中等）

原文：https://www.cnblogs.com/ash98/p/14695934.html