LC 368. 最大整除子集
题目描述
这是 LeetCode 上的 368. 最大整除子集 ，难度为 中等。
给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
- answer[i] % answer[j] == 0 ，或
- answer[j] % answer[i] == 0
如果存在多个有效解子集，返回其中任何一个均可。
示例 1：1
2
3
4
5输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。
示例 2：1
2
3输入：nums = [1,2,4,8]
输出：[1,2,4,8]
提示：
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 2 * $10^9$
- nums 中的所有整数 互不相同
基本分析
根据题意：对于符合要求的「整除子集」中的任意两个值，必然满足「较大数」是「较小数」的倍数。
数据范围是 $10^3$，我们不可能采取获取所有子集，再检查子集是否合法的爆搜解法。
通常「递归」做不了，我们就往「递推」方向去考虑。
由于存在「整除子集」中任意两个值必然存在倍数/约数关系的性质，我们自然会想到对 nums 进行排序，然后从集合 nums 中从大到小进行取数，每次取数只考虑当前决策的数是否与「整除子集」中的最后一个数成倍数关系即可。
这时候你可能会想枚举每个数作为「整除子集」的起点，然后从前往后遍历一遍，每次都将符合「与当前子集最后一个元素成倍数」关系的数加入答案。
举个🌰，假设有原数组 [1,2,4,8]，“或许”我们期望的决策过程是：
- 遍历到数字
1，此时「整除子集」为空，加到「整除子集」中； - 遍历到数字
2，与「整除子集」的最后一个元素（1）成倍数关系，加到「整除子集」中； - 遍历到数字
4，与「整除子集」的最后一个元素（2）成倍数关系，自然也与2之前的元素成倍数关系，加到「整除子集」中； - 遍历到数字
8，与「整除子集」的最后一个元素（4）成倍数关系，自然也与4之前的元素成倍数关系，加到「整除子集」中。
但这样的做法只能够确保得到「合法解」，无法确保得到的是「最长整除子集」。
当时担心本题数据太弱，上述错误的解法也能够通过，所以还特意实现了一下，还好被卡住了（🤣
同时也得到这个反例：[9,18,54,90,108,180,360,540,720]，如果按照我们上述逻辑，我们得到的是 [9,18,54,108,540] 答案（长度为 5），但事实上存在更长的「整除子集」： [9,18,90,180,360,720]（长度为 6）。
其本质是因为同一个数的不同倍数之间不存在必然的「倍数/约数关系」，而只存在「具有公约数」的性质，这会导致我们「模拟解法」错过最优解。
比如上述 🌰，54 & 90 和 18 存在倍数关系，但两者本身不存在倍数关系。
因此当我们决策到某一个数 nums[i] 时（nums 已排好序），我们无法直接将 nums[i] 直接接在符合「约数关系」的、最靠近位置 i 的数后面，而是要检查位置 i 前面的所有符合「约数关系」的位置，找一个已经形成「整除子集」长度最大的数。
换句话说，当我们对 nums 排好序并从前往后处理时，在处理到 nums[i] 时，我们希望知道位置 i 之前的下标已经形成的「整除子集」长度是多少，然后从中选一个最长的「整除子集」，将 nums[i] 接在后面（前提是符合「倍数关系」）。
动态规划
基于上述分析，我们不难发现这其实是一个序列 DP 问题：某个状态的转移依赖于与前一个状态的关系。即 nums[i] 能否接在 nums[j] 后面，取决于是否满足 nums[i] % nums[j] == 0 条件。
可看做是「最长上升子序列」问题的变形题。
定义 $f[i]$ 为考虑前 i 个数字，且以第 i 个数为结尾的最长「整除子集」长度。
我们不失一般性的考虑任意位置 i，存在两种情况：
- 如果在
i之前找不到符合条件nums[i] % nums[j] == 0的位置j，那么nums[i]不能接在位置i之前的任何数的后面，只能自己独立作为「整除子集」的第一个数，此时状态转移方程为 $f[i] = 1$； - 如果在
i之前能够找到符合条件的位置j，则取所有符合条件的f[j]的最大值，代表如果希望找到以nums[i]为结尾的最长「整除子集」，需要将nums[i]接到符合条件的最长的nums[j]后面，此时状态转移方程为 $f[i] = f[j] + 1$。
同时由于我们需要输出具体方案，需要额外使用 g[] 数组来记录每个状态是由哪个状态转移而来。
定义 $g[i]$ 为记录 $f[i]$ 是由哪个下标的状态转移而来，如果 $f[i] = f[j] + 1$, 则有 $g[i] = j$。
对于求方案数的题目，多开一个数组来记录状态从何转移而来是最常见的手段。
当我们求得所有的状态值之后，可以对 f[] 数组进行遍历，取得具体的最长「整除子集」长度和对应下标，然后使用 g[] 数组进行回溯，取得答案。
代码：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
41class 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;
}
}
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n)$
证明
之所以上述解法能够成立，问题能够转化为「最长上升子序列（LIS）」问题进行求解，本质是利用了「全序关系」中的「可传递性」。
在 LIS 问题中，我们是利用了「关系运算符 $\geqslant$ 」的传递性，因此当我们某个数 a 能够接在 b 后面，只需要确保 $a \geqslant b$ 成立，即可确保 a 大于等于 b 之前的所有值。
那么同理，如果我们想要上述解法成立，我们还需要证明如下内容：
「倍数/约数关系」具有传递性
由于我们将nums[i]往某个数字后面接时（假设为nums[j]），只检查了其与nums[j]的关系，并没有去检查nums[i]与nums[j]之前的数值是否具有「倍数/约数关系」。
换句话说，我们只确保了最终答案 [a1, a2, a3, ..., an] 相邻两数值之间具有「倍数/约数关系」，并不明确任意两值之间具有「倍数/约数关系」。
因此需要证得由 $a | b$ 和 $b | c$，可推导出 $a | c$ 的传递性：
由 $a | b$ 可得 $b = x a$
由 $b | c$ 可得 $c = y b$
最终有 $c = y b = y x * a$，由于 $x$ 和 $y$ 都是整数，因此可得 $a | c$。
得证「倍数/约数关系」具有传递性。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.368 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
