线性动态规划：最大整除子集

题目描述
给定一个无重复元素的整数数组nums，返回其中最大的子集，使得这个子集中的任意两个元素a和b都满足a % b == 0 或 b % a == 0。如果有多个答案，返回其中任意一个即可。

例如：

• 输入：nums = [1,2,3]
• 输出：[1,2] 或 [1,3]
• 解释：[1,2]中2%1=0，满足条件；[1,3]中3%1=0，也满足条件

解题过程

步骤1：理解问题本质
这个问题要求找到一个最大的子集，其中任意两个元素都能整除。观察发现：

• 如果a能整除b，且b能整除c，那么a能整除c（传递性）
• 这实际上要求子集中的元素构成一个"整除链"

步骤2：排序的重要性
由于整除关系具有方向性，我们可以先对数组排序。这样问题就转化为：在排序后的数组中，找到最长的子序列，使得每个元素都能整除它后面的元素。

例如：[1,2,4,8]就是一个有效的整除子集，因为1|2，2|4，4|8。

步骤3：定义状态
定义dp[i]表示以第i个元素结尾的最长整除子集的长度。

步骤4：状态转移方程
对于每个位置i，我们需要检查所有j < i：

• 如果nums[i] % nums[j] == 0，说明nums[j]可以接在nums[i]前面
• 此时dp[i] = max(dp[i], dp[j] + 1)

步骤5：记录路径
为了最终能输出具体的子集（而不仅仅是长度），我们需要记录每个状态是从哪个状态转移过来的：

• 定义prev[i]表示在最长整除子集中，nums[i]的前一个元素的索引

步骤6：算法步骤

1. 对数组进行排序
2. 初始化dp数组，每个位置初始值为1（至少包含自己）
3. 初始化prev数组，每个位置初始值为-1（表示没有前驱）
4. 遍历数组，对于每个i，遍历所有j < i：
   • 如果nums[i] % nums[j] == 0 且 dp[j] + 1 > dp[i]
   • 更新dp[i] = dp[j] + 1
   • 更新prev[i] = j
5. 找到dp数组中的最大值及其位置
6. 根据prev数组回溯得到具体子集

步骤7：详细示例
以nums = [1,2,4,8]为例：

排序后：[1,2,4,8]

初始化：

• dp = [1,1,1,1]
• prev = [-1,-1,-1,-1]

处理过程：

• i=0：没有j<0，保持dp[0]=1
• i=1：
  • j=0：2%1=0，dp[1]=max(1,1+1)=2，prev[1]=0
• i=2：
  • j=0：4%1=0，dp[2]=max(1,1+1)=2，prev[2]=0
  • j=1：4%2=0，dp[2]=max(2,2+1)=3，prev[2]=1
• i=3：
  • j=0：8%1=0，dp[3]=max(1,1+1)=2，prev[3]=0
  • j=1：8%2=0，dp[3]=max(2,2+1)=3，prev[3]=1
  • j=2：8%4=0，dp[3]=max(3,3+1)=4，prev[3]=2

最终dp=[1,2,3,4]，最大值4在位置3
回溯：3→2→1→0，得到子集[1,2,4,8]

步骤8：时间复杂度优化
当前算法时间复杂度为O(n²)，空间复杂度为O(n)。对于较大的n，这是可以接受的，因为题目约束通常n≤1000。

步骤9：边界情况处理

• 空数组：返回空集
• 单元素数组：返回包含该元素的集合
• 所有元素互质：返回任意一个元素（因为任意两个数都不能整除）

步骤10：完整实现思路

def largestDivisibleSubset(nums):
    if not nums:
        return []
    
    nums.sort()
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    max_len = 1
    max_idx = 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
                prev[i] = j
        if dp[i] > max_len:
            max_len = dp[i]
            max_idx = i
    
    # 回溯构建结果
    result = []
    idx = max_idx
    while idx != -1:
        result.append(nums[idx])
        idx = prev[idx]
    
    return result[::-1]  # 反转得到正确顺序

这个算法能够高效地找到最大的整除子集，核心在于利用排序将问题转化为寻找最长整除链，并通过动态规划记录最优解的形成路径。