LeetCode 368. 最大整除子集

2023-05-01 HGNULB 约 7 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 368. 最大整除子集

题意分析

给一个由互不相同的正整数组成的数组 nums，要找出一个尽可能大的子集，使得子集里任意两个元素 $a$、$b$ 都满足 $a \% b = 0$ 或 $b \% a = 0$。答案不唯一时返回任意一个。注意返回的是子集本身（元素列表），不是长度。

「任意两个都要整除」这个条件看起来是 $O(size^2)$ 个约束，但它有一条极其关键的性质可以化简：整除关系具有传递性。如果 $a \mid b$ 且 $b \mid c$，那么必然 $a \mid c$。

由此推出：把子集里的元素按升序排列后，只要相邻两项满足整除（前一项整除后一项），整个子集就自动两两满足条件。于是约束从「两两」降成了「相邻」，问题结构一下子变成了链式的——这正是能用按位置递推求解的前提。

「元素互不相同」这条也不能忽略：它保证排序后严格递增，不会出现两个相等元素导致 $a \mid b$ 与 $b \mid a$ 同时成立的退化情况，也让「小的整除大的」这个方向唯一确定。

求的是最优子集而不是最优值，说明必须记录构造路径，光有长度不够。这是本题相对纯粹的最长链问题多出来的一层要求。

数据规模：nums 长度到 1000，所以 $O(n^2)$ 的两两枚举（$10^6$）完全可行，不必追求更优。

边界：数组只有一个元素时返回它自己（单元素子集平凡满足条件）；任何两个元素都不互相整除时（如 [2,3,5]）答案是任意一个单元素子集，长度为 1 而不是 0；题目保证数组非空。

解法：排序 + DP 记录前驱

核心思路

先升序排序。整除具有传递性，因此一条升序链只要相邻元素满足整除，链内任意两项也满足题意。

定义 dp[i] 为以 nums[i] 结尾的最大整除子集长度，prev[i] 为该最优链中 nums[i] 的前驱下标。枚举 j<i，若 nums[i] % nums[j] == 0，就可以把 nums[i] 接在以 j 结尾的链后；严格变长时同步更新两个数组。

不变量：完成下标 i 后，dp[i] 是所有以 nums[i] 结尾的合法链最大长度，沿 prev 恰能还原其中一条。

正确性：排序保证合法前驱一定更小并位于前面。任意最优链去掉末项后，必然是某个可整除前驱结尾的合法链；转移枚举了这个前驱。反过来，由整除传递性，任何被转移接上的链仍满足两两整除。最后从全局最长状态沿前驱回溯，即得到最大子集。

解题步骤

升序排序，初始化 dp[i]=1、prev[i]=-1。

对每个 i 枚举 j<i，满足整除且链更长时同步更新长度和前驱。

记录最长链的结尾 bestEnd。

从 bestEnd 沿 prev 回溯，得到逆序链后反转。

[3,4,16,8] 排序为 [3,4,8,16]，状态链为 4 <- 8 <- 16，回溯并反转得到 [4,8,16]。

边界 [2,3,5] 中没有可连接的两项，每个 dp 都为 1，最终应返回任意单元素子集而不是空列表。

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

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^2)$，排序的 $O(n\log n)$ 被双层转移覆盖。

空间复杂度：$O(n)$，用于 dp、prev 和返回结果。

关键点总结

排序把整除关系统一成“小数在前、大数在后”的单向依赖。

整除传递性保证只需检查新末项与链末项。

dp 求长度，prev 保存同一条最优链的前驱；二者必须同步更新。

最优结尾未必是数组最后一个位置，需要单独维护 bestEnd。

回溯方向从大到小，返回前要反转。

易错点总结

不排序：[4,2,8] 会漏掉前驱 2，无法得到 [2,4,8]。

dp 初值为 0：互不整除的数组会错误返回空集。

prev 初值为 0：从下标 0 回溯时形成自环；无前驱应使用 -1。

只判断整除、不判断候选链更长：prev 可能被较短链覆盖，与 dp 长度不一致。

取模方向写反：排序后应检查大数 nums[i] 是否能被小数 nums[j] 整除。

直接从最后一个元素回溯：最长链可能在更早位置结束，例如 [1,2,4,5]。

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	转移条件换成比较大小，因而可用贪心加二分优化到 $O(n \log n)$，本题不能
354. 俄罗斯套娃信封问题	困难	二维偏序，需先按宽升序、等宽时高降序排序，把问题降成一维 LIS
673. 最长递增子序列的个数	中等	除长度外还要统计方案数，需额外维护 `count` 数组并处理等长时的累加
1048. 最长字符串链	中等	前驱关系是「删一个字符可得」，按长度排序后用哈希表直接查前驱，无需双层循环
面试题 08.13. 堆箱子	困难	三维严格偏序，排序后仍需 $O(n^2)$ 转移，且求的是高度和而非个数
面试题 17.08. 马戏团人塔	中等	与 354 同构，重点在等高时按体重降序排序以避免同高误接
53. 最大子数组和	中等	同为「以第 i 项结尾」的状态定义，但只依赖前一项，用来对照理解转移的依赖范围