给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对
(answer[i], answer[j]) 都应当满足：
answer[i] % answer[j] == 0 ，或answer[j] % answer[i] == 0
如果存在多个有效解子集，返回其中任何一个均可。
示例 1：
**输入：** nums = [1,2,3]
**输出：** [1,2]
**解释：** [1,3] 也会被视为正确答案。
示例 2：
**输入：** nums = [1,2,4,8]
**输出：** [1,2,4,8]
提示：
1 <= nums.length <= 10001 <= nums[i] <= 2 * 109nums 中的所有整数 互不相同
前言
首先需要理解什么叫「整除子集」。根据题目的描述，如果一个所有元素互不相同的集合中的任意元素存在整除关系，就称为整除子集。为了得到「最大整除子集」，我们需要考虑如何从一个小的整除子集扩充成为更大的整除子集。
根据整除关系具有传递性，即如果 $a\big|b$，并且 $b\big|c$，那么 $a\big|c$，可知：
这两点揭示了当前问题状态转移的特点，因此可以使用动态规划的方法求解。题目只要求我们得到多个目标子集的其中一个，根据求解动态规划问题的经验，我们需要将子集的大小定义为状态，然后根据结果倒推得到一个目标子集。事实上，当前问题和使用动态规划解决的经典问题「300. 最长递增子序列 」有相似之处。
方法一：动态规划
根据前言的分析，我们需要将输入数组 nums 按照升序排序，以便获得一个子集的最小整数或者最大整数。又根据动态规划的「无后效性」状态设计准则，我们需要将状态定义成「某个元素必须选择」。
状态定义：dp}[i]$ 表示在输入数组 nums 升序排列的前提下，以 nums}[i]$ 为最大整数的「整除子集」的大小（在这种定义下 nums}[i]$ 必须被选择）。
状态转移方程：枚举 $j = 0 \ldots i-1$ 的所有整数 nums}[j]$，如果 nums}[j]$ 能整除 nums}[i]$，说明 nums}[i]$ 可以扩充在以 nums}[j]$ 为最大整数的整除子集里成为一个更大的整除子集。
初始化：由于 nums}[i]$ 必须被选择，因此对于任意 $i = 0 \ldots n-1$，初始的时候 dp}[i] = 1$，这里 $n$ 是输入数组的长度。
输出：由于最大整除子集不一定包含 nums 中最大的整数，所以我们需要枚举所有的 dp}[i]$，选出最大整除子集的大小 maxSize，以及该最大子集中的最大整数 maxVal。按照如下方式倒推获得一个目标子集：
倒序遍历数组 dp，直到找到 dp}[i] = \textit{maxSize 为止，把此时对应的 nums}[i]$ 加入结果集，此时 maxVal} = \textit{nums}[i]$；
然后将 maxSize 的值减 $1$，继续倒序遍历找到 dp}[i] = \textit{maxSize，且 nums}[i]$ 能整除 maxVal 的 $i$ 为止，将此时的 nums}[i]$ 加入结果集，maxVal 更新为此时的 $num[i]$；
重复上述操作，直到 maxSize 的值变成 $0$，此时的结果集即为一个目标子集。
下面用一个例子说明如何得到最大整除子集。假设输入数组为 $[2,4,7,8,9,12,16,18]$（已经有序），得到的动态规划表格如下：
| nums |
$2$ |
$4$ |
$7$ |
$8$ |
$9$ |
$12$ |
$16$ |
$20$ |
| dp |
$1$ |
$2$ |
$1$ |
$3$ |
$1$ |
$3$ |
$4$ |
$3$ |
得到最大整除子集的做法如下：
根据 dp 的计算结果，maxSize}=4$，maxVal}=16$，因此大小为 $4$ 的最大整除子集包含的最大整数为 $16$；
然后查找大小为 $3$ 的最大整除子集，我们看到 $8$ 和 $12$ 对应的状态值都是 $3$，最大整除子集一定包含 $8$，这是因为 $8 \big| 16$；
然后查找大小为 $2$ 的最大整除子集，我们看到 $4$ 对应的状态值是 $2$，最大整除子集一定包含 $4$；
然后查找大小为 $1$ 的最大整除子集，我们看到 $2$ 对应的状态值是 $1$，最大整除子集一定包含 $2$。
通过这样的方式，我们就找到了满足条件的某个最大整除子集 $[16,8,4,2]$。
代码
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int len = nums.length;
Arrays.sort(nums);
int[] dp = new int[len];
Arrays.fill(dp, 1);
int maxSize = 1;
int maxVal = dp[0];
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
if (dp[i] > maxSize) {
maxSize = dp[i];
maxVal = nums[i];
}
}
List<Integer> res = new ArrayList<Integer>();
if (maxSize == 1) {
res.add(nums[0]);
return res;
}
for (int i = len - 1; i >= 0 && maxSize > 0; i--) {
if (dp[i] == maxSize && maxVal % nums[i] == 0) {
res.add(nums[i]);
maxVal = nums[i];
maxSize--;
}
}
return res;
}
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| var largestDivisibleSubset = function(nums) {
const len = nums.length;
nums.sort((a, b) => a - b);
const dp = new Array(len).fill(1);
let maxSize = 1;
let maxVal = dp[0];
for (let i = 1; i < len; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] % nums[j] === 0) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
if (dp[i] > maxSize) {
maxSize = dp[i];
maxVal = nums[i];
}
}
const res = [];
if (maxSize === 1) {
res.push(nums[0]);
return res;
}
for (let i = len - 1; i >= 0 && maxSize > 0; i--) {
if (dp[i] === maxSize && maxVal % nums[i] === 0) {
res.push(nums[i]);
maxVal = nums[i];
maxSize--;
}
}
return res;
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| func largestDivisibleSubset(nums []int) (res []int) {
sort.Ints(nums)
n := len(nums)
dp := make([]int, n)
for i := range dp {
dp[i] = 1
}
maxSize, maxVal := 1, 1
for i := 1; i < n; i++ {
for j, v := range nums[:i] {
if nums[i]%v == 0 && dp[j]+1 > dp[i] {
dp[i] = dp[j] + 1
}
}
if dp[i] > maxSize {
maxSize, maxVal = dp[i], nums[i]
}
}
if maxSize == 1 {
return []int{nums[0]}
}
for i := n - 1; i >= 0 && maxSize > 0; i-- {
if dp[i] == maxSize && maxVal%nums[i] == 0 {
res = append(res, nums[i])
maxVal = nums[i]
maxSize--
}
}
return
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
int len = nums.size();
sort(nums.begin(), nums.end());
vector<int> dp(len, 1);
int maxSize = 1;
int maxVal = dp[0];
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
if (dp[i] > maxSize) {
maxSize = dp[i];
maxVal = nums[i];
}
}
vector<int> res;
if (maxSize == 1) {
res.push_back(nums[0]);
return res;
}
for (int i = len - 1; i >= 0 && maxSize > 0; i--) {
if (dp[i] == maxSize && maxVal % nums[i] == 0) {
res.push_back(nums[i]);
maxVal = nums[i];
maxSize--;
}
}
return res;
}
};
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| int cmp(int* a, int* b) {
return *a - *b;
}
int* largestDivisibleSubset(int* nums, int numsSize, int* returnSize) {
int len = numsSize;
qsort(nums, numsSize, sizeof(int), cmp);
int dp[len];
for (int i = 0; i < len; i++) {
dp[i] = 1;
}
int maxSize = 1;
int maxVal = dp[0];
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0) {
dp[i] = fmax(dp[i], dp[j] + 1);
}
}
if (dp[i] > maxSize) {
maxSize = dp[i];
maxVal = nums[i];
}
}
int* res = malloc(sizeof(int) * len);
*returnSize = 0;
if (maxSize == 1) {
res[(*returnSize)++] = nums[0];
return res;
}
for (int i = len - 1; i >= 0 && maxSize > 0; i--) {
if (dp[i] == maxSize && maxVal % nums[i] == 0) {
res[(*returnSize)++] = nums[i];
maxVal = nums[i];
maxSize--;
}
}
return res;
}
|
复杂度分析
4 月 22 日至 4 月 28 日，进入「学习 」，完成页面右上角的「让时间更有价值」限时阅读任务，可获得「2021 读书日纪念勋章」。更多活动详情戳上方标题了解更多👆
今日学习任务：
