LeetCode 368. 最大整除子集
题目描述
题意分析
从互不相同的正整数中选择尽量多的元素，使选出元素的任意一对都满足一方能整除另一方。要求返回具体子集，而不只是长度；若有多个同样大的合法子集，返回任意一个即可。
解法：排序 + DP 记录前驱
核心思路
[!blue]
先把数组升序排序。对于两个不同的正整数，只有较小者可能整除较大者，所以合法子集排序后一定从小到大连接。又因为整除具有传递性，只要链上相邻元素满足前者整除后者，更早的每个元素也都能整除更后的元素。于是“两两满足整除”就转成了“寻找最长整除链”。
定义
dp[i]为以nums[i]作为最大元素、也就是链尾的最长链长度。单个元素始终合法，因此初始dp[i] = 1。枚举所有j < i，若nums[i] % nums[j] == 0，就可以把nums[i]接到以nums[j]结尾的最长链后面，得到候选长度dp[j] + 1。接入新元素时，只检查链尾就足够：前面所有元素已经整除
nums[j]，而nums[j]又整除nums[i]，传递性保证新元素与整条链都满足要求。反过来，一条以nums[i]结尾且长度超过一的最优链，倒数第二项一定是某个满足条件的j，因此枚举所有j不会遗漏最优方案。为返回具体子集，
prev[i]记录当前最优链中i的前驱下标，初始为 $-1$，表示这条链只有自身。只有候选长度严格更大时，才同时更新dp[i]和prev[i]，保证长度与回溯路径来自同一个选择；等长时保留任意一条即可。一边完成各个
dp[i]，一边记录全局最长长度bestLen及末尾bestEnd。最优链不一定包含数组最大值，所以不能固定从最后一个位置还原。应从bestEnd沿prev回溯，直到 $-1$；前驱下标始终更小，回溯一定结束，取得的元素正好构成对应最长链。当前实现再反转一次，使结果按升序展示。只有一个元素或没有任何两个元素能整除时，所有候选都保持单元素链，依然可以从全局最佳末尾返回一个合法最大子集。
解题步骤
- 排序，所有长度初始化为一，前驱初始化为 -1。
- 枚举 i 及此前的 j，满足整除且链更长时更新。
- 记录最长链末尾。
- 沿前驱还原并返回结果。
代码实现
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int[] dp = new int[n];
int[] prev = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = 1;
prev[i] = -1;
}
int bestLen = 0;
int bestEnd = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
// 更长链出现时同步保存长度和对应前驱。
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
if (dp[i] > bestLen) {
bestLen = dp[i];
bestEnd = i;
}
}
List<Integer> res = new ArrayList<>();
// 从全局最佳末尾沿前驱还原，不一定从数组最后一项开始。
int cur = bestEnd;
while (cur != -1) {
res.add(nums[cur]);
cur = prev[cur];
}
Collections.reverse(res);
return res;
}
}
import "sort"
func largestDivisibleSubset(nums []int) []int {
sort.Ints(nums)
n := len(nums)
dp := make([]int, n)
prev := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = 1
prev[i] = -1
}
bestLen := 0
bestEnd := -1
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
if nums[i]%nums[j] == 0 && dp[j]+1 > dp[i] {
// 更长链出现时同步保存长度和对应前驱。
dp[i] = dp[j] + 1
prev[i] = j
}
}
if dp[i] > bestLen {
bestLen = dp[i]
bestEnd = i
}
}
res := make([]int, 0)
// 从全局最佳末尾沿前驱还原，不一定从数组最后一项开始。
cur := bestEnd
for cur != -1 {
res = append(res, nums[cur])
cur = prev[cur]
}
for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
res[i], res[j] = res[j], res[i]
}
return res
}
复杂度分析
- 时间复杂度：$O(n²)$，双层转移占主导。
- 空间复杂度：$O(n)$，保存长度、前驱及结果；输入数组会被排序。
关键点总结
[!green]
- 相邻整除通过传递性保证两两整除。
- 长度和前驱必须对应同一条选中的链。
- 最长链末尾不一定是数组最大值。
易错点总结
[!yellow]
- 不排序仍只查此前元素：可能遗漏数值更小但位置更后的前驱。
- 前驱默认零：回溯可能停在零下标形成自环。
- 只要整除就覆盖前驱：较短链可能覆盖更好的方案。
- 直接从最后一项回溯：数组最大值不一定能接在最优链后面，应使用单独记录的
bestEnd。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 300. 最长递增子序列 | 中等 | 排序后同样用以某项结尾的最长链DP，本题转移条件是整除而不是仅数值递增。 |
| 873. 最长的斐波那契子序列的长度 | 中等 | 同样要记录可延续的序列状态，本题只依赖末项，斐波那契条件则依赖最后两项。 |