最大整除子集

字数 2585 2025-12-09 16:02:17

最大整除子集

问题描述

给定一个不含重复元素的整数数组 nums，找到并返回其中最大的子集，使得这个子集中的任意两个元素 (a, b) 都满足 a % b == 0 或 b % a == 0。如果有多个答案，返回其中任何一个即可。

示例 1

输入：nums = [1, 2, 3]
输出：[1, 2] 或 [1, 3]
解释：[1, 2] 和 [1, 3] 都满足条件，其中[2, 3]不满足因为2%3不等于0，3%2也不等于0。

示例 2

输入：nums = [1, 2, 4, 8]
输出：[1, 2, 4, 8]
解释：这个子集内任意两个元素都满足整除条件。

解题思路详解

这个问题是“最长递增子序列”的一个变种，关键在于找出最长的序列，使得序列中后面的每个元素都是前面某个元素的倍数（或反过来）。为了应用动态规划，我们首先对数组排序，这样我们只需要关心前面的元素能否整除后面的元素。

核心思想：
如果我们定义 dp[i] 表示以第 i 个元素（排序后）为结尾的最大整除子集的长度，那么状态转移就是：遍历 i 之前的所有位置 j (0 <= j < i)，如果 nums[i] % nums[j] == 0，说明 nums[i] 可以被加入到以 nums[j] 结尾的子集中，形成一个更长的子集。因此，dp[i] = max(dp[j] + 1) 对所有满足整除条件的 j 取最大值。

但仅仅知道长度还不够，我们还需要知道具体的子集是什么。所以，我们需要额外记录每个位置 i 的前驱位置 pre[i]，即从哪个 j 转移而来能得到最大长度。这样，当我们找到拥有最大 dp 值的那个位置 i_max 后，就可以通过 pre 数组反向回溯，构造出这个最大整除子集。

步骤拆解

排序：
首先对 nums 进行升序排序。排序的目的是让“整除”关系变成单向的：如果 a <= b 且 a 能整除 b，那么 a 一定在 b 的前面。这样，我们只需要检查前面的数是否能整除后面的数，无需再检查后面的数整除前面的数。这大大简化了问题。
初始化动态规划数组：
- 定义 n = len(nums)。
- 定义 dp = [1] * n。dp[i] 的初始值是1，因为任何单个元素本身就构成了一个大小为1的整除子集。
- 定义 pre = [-1] * n。pre[i] 记录在形成最大子集时，nums[i] 的前一个元素的下标。初始为-1，表示没有前驱。
状态转移：
我们使用两层循环：
- 外层循环 i 从 0 到 n-1，表示当前正在计算以 nums[i] 结尾的最大整除子集。
- 内层循环 j 从 0 到 i-1，寻找能转移到 i 的前驱。
- 对于每对 (j, i)，检查整除条件：nums[i] % nums[j] == 0。
- 如果条件满足，我们检查 dp[j] + 1 是否大于当前的 dp[i]。如果是，说明找到了一个更长的以 nums[i] 结尾的子集。那么我们就更新：
  - dp[i] = dp[j] + 1
  - pre[i] = j （记录前驱）
记录最大长度和结束位置：
在填充 dp 数组的过程中，我们同步记录遇到的最大长度 max_len 和达到这个最大长度的位置 max_index。这样在动态规划结束后，我们就能立刻知道从哪个位置开始回溯。
回溯构造结果：
从 max_index 开始，根据 pre 数组向前回溯。将沿途的 nums[index] 加入到结果列表中。因为回溯是从子集的最后一个元素开始的，所以最终需要将结果列表反转，得到从小到大顺序的正确子集。
返回结果。

举例说明：

以 nums = [1, 2, 4, 8] 为例。

排序后仍为 [1, 2, 4, 8]。
初始化：dp = [1, 1, 1, 1]， pre = [-1, -1, -1, -1]， max_len = 1, max_index = 0。
状态转移：
- i=0：没有 j，跳过。dp=[1,1,1,1], pre不变。
- i=1：
  - j=0: nums[1]%nums[0]=2%1=0 满足。dp[0]+1=2 > dp[1]=1，所以 dp[1]=2， pre[1]=0。
  - 此时 dp[1]=2 > max_len=1，更新 max_len=2, max_index=1。
- i=2：
  - j=0: 4%1=0， dp[0]+1=2 > dp[2]=1，更新 dp[2]=2, pre[2]=0。
  - j=1: 4%2=0， dp[1]+1=3 > dp[2]=2，更新 dp[2]=3, pre[2]=1。
  - 此时 dp[2]=3 > max_len=2，更新 max_len=3, max_index=2。
- i=3：
  - j=0: 8%1=0， dp[0]+1=2，更新 dp[3]=2, pre[3]=0。
  - j=1: 8%2=0， dp[1]+1=3，更新 dp[3]=3, pre[3]=1。
  - j=2: 8%4=0， dp[2]+1=4，更新 dp[3]=4, pre[3]=2。
  - 此时 dp[3]=4 > max_len=3，更新 max_len=4, max_index=3。
最终，max_len=4， max_index=3。
回溯：从 index=3 开始，pre[3]=2 -> pre[2]=1 -> pre[1]=0 -> pre[0]=-1。对应的数字序列是 nums[3]=8， nums[2]=4， nums[1]=2， nums[0]=1。
反转序列，得到结果 [1, 2, 4, 8]。

算法复杂度：

时间复杂度：O(n²)。主要开销是两重循环，外层循环n次，内层循环平均n/2次。
空间复杂度：O(n)。用于存储 dp 和 pre 数组。

总结：
这道题的核心是将寻找“任意两数可整除”的子集问题，通过排序转化为类似最长递增子序列（LIS）的动态规划问题。dp[i] 记录以 i 结尾的最长子集长度，pre[i] 记录转移路径以便最终构造答案。这是一个经典的“动态规划+路径记录”问题。

最大整除子集问题描述给定一个不含重复元素的整数数组 nums ，找到并返回其中最大的子集，使得这个子集中的任意两个元素 (a, b) 都满足 a % b == 0 或 b % a == 0 。如果有多个答案，返回其中任何一个即可。示例 1 示例 2 解题思路详解这个问题是“最长递增子序列”的一个变种，关键在于找出最长的序列，使得序列中后面的每个元素都是前面某个元素的倍数（或反过来）。为了应用动态规划，我们首先对数组排序，这样我们只需要关心前面的元素能否整除后面的元素。核心思想：如果我们定义 dp[i] 表示以第 i 个元素（排序后）为结尾的最大整除子集的长度，那么状态转移就是：遍历 i 之前的所有位置 j (0 <= j < i)，如果 nums[i] % nums[j] == 0 ，说明 nums[i] 可以被加入到以 nums[j] 结尾的子集中，形成一个更长的子集。因此， dp[i] = max(dp[j] + 1) 对所有满足整除条件的 j 取最大值。但仅仅知道长度还不够，我们还需要知道具体的子集是什么。所以，我们需要额外记录每个位置 i 的前驱位置 pre[i] ，即从哪个 j 转移而来能得到最大长度。这样，当我们找到拥有最大 dp 值的那个位置 i_max 后，就可以通过 pre 数组反向回溯，构造出这个最大整除子集。步骤拆解排序：首先对 nums 进行升序排序。排序的目的是让“整除”关系变成单向的：如果 a <= b 且 a 能整除 b ，那么 a 一定在 b 的前面。这样，我们只需要检查前面的数是否能整除后面的数，无需再检查后面的数整除前面的数。这大大简化了问题。初始化动态规划数组：定义 n = len(nums) 。定义 dp = [1] * n 。 dp[i] 的初始值是1，因为任何单个元素本身就构成了一个大小为1的整除子集。定义 pre = [-1] * n 。 pre[i] 记录在形成最大子集时， nums[i] 的前一个元素的下标。初始为-1，表示没有前驱。状态转移：我们使用两层循环：外层循环 i 从 0 到 n-1 ，表示当前正在计算以 nums[i] 结尾的最大整除子集。内层循环 j 从 0 到 i-1 ，寻找能转移到 i 的前驱。对于每对 (j, i) ，检查整除条件： nums[i] % nums[j] == 0 。如果条件满足，我们检查 dp[j] + 1 是否大于当前的 dp[i] 。如果是，说明找到了一个更长的以 nums[i] 结尾的子集。那么我们就更新： dp[i] = dp[j] + 1 pre[i] = j （记录前驱）记录最大长度和结束位置：在填充 dp 数组的过程中，我们同步记录遇到的最大长度 max_len 和达到这个最大长度的位置 max_index 。这样在动态规划结束后，我们就能立刻知道从哪个位置开始回溯。回溯构造结果：从 max_index 开始，根据 pre 数组向前回溯。将沿途的 nums[index] 加入到结果列表中。因为回溯是从子集的最后一个元素开始的，所以最终需要将结果列表反转，得到从小到大顺序的正确子集。返回结果。举例说明：以 nums = [1, 2, 4, 8] 为例。排序后仍为 [1, 2, 4, 8] 。初始化： dp = [1, 1, 1, 1] ， pre = [-1, -1, -1, -1] ， max_len = 1 , max_index = 0 。状态转移： i=0 ：没有 j ，跳过。 dp=[1,1,1,1] , pre 不变。 i=1 ： j=0 : nums[1]%nums[0]=2%1=0 满足。 dp[0]+1=2 > dp[1]=1 ，所以 dp[1]=2 ， pre[1]=0 。此时 dp[1]=2 > max_len=1 ，更新 max_len=2 , max_index=1 。 i=2 ： j=0 : 4%1=0 ， dp[0]+1=2 > dp[2]=1 ，更新 dp[2]=2 , pre[2]=0 。 j=1 : 4%2=0 ， dp[1]+1=3 > dp[2]=2 ，更新 dp[2]=3 , pre[2]=1 。此时 dp[2]=3 > max_len=2 ，更新 max_len=3 , max_index=2 。 i=3 ： j=0 : 8%1=0 ， dp[0]+1=2 ，更新 dp[3]=2 , pre[3]=0 。 j=1 : 8%2=0 ， dp[1]+1=3 ，更新 dp[3]=3 , pre[3]=1 。 j=2 : 8%4=0 ， dp[2]+1=4 ，更新 dp[3]=4 , pre[3]=2 。此时 dp[3]=4 > max_len=3 ，更新 max_len=4 , max_index=3 。最终， max_len=4 ， max_index=3 。回溯：从 index=3 开始， pre[3]=2 -> pre[2]=1 -> pre[1]=0 -> pre[0]=-1 。对应的数字序列是 nums[3]=8 ， nums[2]=4 ， nums[1]=2 ， nums[0]=1 。反转序列，得到结果 [1, 2, 4, 8] 。算法复杂度：时间复杂度：O(n²)。主要开销是两重循环，外层循环n次，内层循环平均n/2次。空间复杂度：O(n)。用于存储 dp 和 pre 数组。总结：这道题的核心是将寻找“任意两数可整除”的子集问题，通过排序转化为类似最长递增子序列（LIS）的动态规划问题。 dp[i] 记录以 i 结尾的最长子集长度， pre[i] 记录转移路径以便最终构造答案。这是一个经典的“动态规划+路径记录”问题。