最大整除子集 图解题解
这道题到底在问什么
- 输入
- nums=[1,2,4,8]
- 输出
- [1,2,4,8](整条链都两两整除)
- 输入
- nums=[3,4,16,8]
- 输出
- [4,8,16](排序后做 DP)
最优解：一步一步想明白
- 3记住「排序 → dp[i] 看前面能整除它的、取最长 +1 并记前驱 → 从最长处回溯」,下面逐步套它。
- 4先排序:[5, 9, 18, 54, 108]。排序后只需考虑「大数能否被前面的小数整除」,把问题变成从左到右的链式 DP。
- 5轮到 5(紫)。它自己至少是长度 1 的链。回看前面的数,谁能整除它、就尝试接到谁后面变更长。
- 6定下 dp[0]=1。目前全局最长链的结尾是 5(长度 1)。
- 7轮到 9(紫)。它自己至少是长度 1 的链。回看前面的数,谁能整除它、就尝试接到谁后面变更长。
- 89 不能被 5 整除(灰),跳过这个候选。
- 9定下 dp[1]=1。目前全局最长链的结尾是 5(长度 1)。
- 10轮到 18(紫)。它自己至少是长度 1 的链。回看前面的数,谁能整除它、就尝试接到谁后面变更长。
- 1118 不能被 5 整除(灰),跳过这个候选。
- 1218 能被 9 整除,且接到 9 的链(长 1)后更长。更新 dp[2]=2,记 18 的前驱是 9。
- 13定下 dp[2]=2。目前全局最长链的结尾是 18(长度 2)。
- 14轮到 54(紫)。它自己至少是长度 1 的链。回看前面的数,谁能整除它、就尝试接到谁后面变更长。
- 1554 不能被 5 整除(灰),跳过这个候选。
- 1654 能被 9 整除,且接到 9 的链(长 1)后更长。更新 dp[3]=2,记 54 的前驱是 9。
- 1754 能被 18 整除,且接到 18 的链(长 2)后更长。更新 dp[3]=3,记 54 的前驱是 18。
- 18定下 dp[3]=3。目前全局最长链的结尾是 54(长度 3)。
- 19轮到 108(紫)。它自己至少是长度 1 的链。回看前面的数,谁能整除它、就尝试接到谁后面变更长。
- 20108 不能被 5 整除(灰),跳过这个候选。
- 21108 能被 9 整除,且接到 9 的链(长 1)后更长。更新 dp[4]=2,记 108 的前驱是 9。
- 22108 能被 18 整除,且接到 18 的链(长 2)后更长。更新 dp[4]=3,记 108 的前驱是 18。
- 23108 能被 54 整除,且接到 54 的链(长 3)后更长。更新 dp[4]=4,记 108 的前驱是 54。
- 24定下 dp[4]=4。目前全局最长链的结尾是 108(长度 4)。
- 25回溯第 1 步:收下 108,再跳到它的前驱 54。绿色是已收集进最大整除子集的数。
- 26回溯第 2 步:收下 54,再跳到它的前驱 18。绿色是已收集进最大整除子集的数。
- 27回溯第 3 步:收下 18,再跳到它的前驱 9。绿色是已收集进最大整除子集的数。
- 28回溯第 4 步:收下 9,它没有前驱,链到头了。绿色是已收集进最大整除子集的数。
- 29回溯结束,最大整除子集 = [9, 18, 54, 108]。链上相邻两数整除(9→18→54→108),靠整除的传递性,任意两数也都整除。
⚠️ 容易写错的地方
✗ 错：不排序直接 DP
✓ 对：必须先从小到大排序
排序后才能保证「能整除的小数一定在前面」,只往左看 j<i 即可;不排序会漏掉前后顺序乱的整除关系
✗ 错：只求最长长度、不记前驱
✓ 对：用 parent 数组记每步的前一个下标
本题要返回具体子集而非长度,必须靠 parent 回溯还原链;只记 dp 长度无法重建子集
✗ 错：担心链上不相邻的两数不整除
✓ 对：整除有传递性,相邻整除即全体整除
若 a|b 且 b|c 则 a|c;链上每对相邻都整除,任意两数也整除,无需两两验证
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
nums.sort()
n = len(nums)
dp = [1] * n
parent = [-1] * n
best = 0
for i in range(n):
for j in range(i):
if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
parent[i] = j
if dp[i] > dp[best]:
best = i
ans = []
while best != -1:
ans.append(nums[best])
best = parent[best]
return ansC++
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size(), best = 0;
vector<int> dp(n, 1), parent(n, -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; parent[i] = j;
}
if (dp[i] > dp[best]) best = i;
}
vector<int> ans;
while (best != -1) { ans.push_back(nums[best]); best = parent[best]; }
return ans;
}
};Java
import java.util.*;
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
int n = nums.length, best = 0;
int[] dp = new int[n], parent = new int[n];
Arrays.fill(dp, 1); Arrays.fill(parent, -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; parent[i] = j;
}
if (dp[i] > dp[best]) best = i;
}
List<Integer> ans = new ArrayList<>();
while (best != -1) { ans.add(nums[best]); best = parent[best]; }
return ans;
}
}复杂度
时间
O(n²)
n 是数组长度。排序 O(n log n);DP 是双重循环 O(n²),取模判整除是 O(1);回溯 O(n)。整体由 O(n²) 主导
空间
O(n)
dp 与 parent 数组各 O(n),答案子集 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大整除子集 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题和最长递增子序列(LIS)有什么异同?+
结构几乎一样:都是排序(LIS 本身有序)后的 O(n²) 链式 DP,dp[i] 记以 i 结尾的最长链。区别只在「能否接」的判定:LIS 看 nums[j]<nums[i](严格小),本题看 nums[i]%nums[j]==0(整除)。另外本题要返回具体子集,所以多记一个 parent 回溯。可以说这是「把 LIS 的比较换成整除」的变体。
能不能像 LIS 那样用二分把复杂度降到 O(n log n)?+
不能直接套。LIS 的 O(n log n) 依赖「结尾值单调、可二分」,而整除关系不满足这种全序的二分性质:一个数能接到哪些前驱不是由大小单调决定的(比如 6 能接 2 和 3,但 2、3 互不整除)。所以本题一般停在 O(n²) 的 DP,无法简单二分优化。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最大整除子集 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。