线性动态规划：最大整除子集 题目描述 给定一个由无重复正整数组组成的数组nums，返回其中最大的子集answer，使得answer中的任意两个不同元素都满足：element1 % element2 == 0，或者element2 % element1 == 0。如果存在多个解，返回其中任意一个。 示例： 输入：nums = [ 1, 2, 4, 8 ] 输出：[ 1, 2, 4, 8 ] 解释：这个子集中任意两个元素都满足整除条件，并且是最大的子集。 解题过程 这个问题可以看作是最长递增子序列（LIS）问题的一个变种，但比较的条件从数值大小变成了整除关系。我们需要找到一个最长的序列，其中每个元素都能整除序列中后面的元素（或反之）。为了应用动态规划，一个关键的预处理步骤是对数组进行排序。 步骤1：问题分析与排序预处理 核心观察：如果在一个整除子集中有a | b（a整除b）且b | c，那么根据整除的传递性，必然有a | c。因此，如果我们对数组进行排序，那么一个有效的整除子集必然是一个"整除链"，即链中每个元素都能整除下一个元素。例如，[ 1, 2, 4, 8 ]就是一个整除链（1|2, 2|4, 4|8）。 排序的好处：排序后，我们只需要考虑每个元素与其后面的元素的整除关系（因为如果a <b，那么只可能是a整除b，而不可能是b整除a）。这大大简化了状态转移的考虑。 因此，首先对数组nums进行升序排序：sortedNums = sorted(nums) 步骤2：定义动态规划状态 定义dp[ i]：表示以排序后数组中第i个元素（即sortedNums[ i]）作为 最大元素 （即整除链中的最后一个元素）时，所能构成的最长整除子集的长度。 为什么定义成“以i结尾”？这是线性DP中常见的子问题定义方式，类似于LIS问题。通过计算每个位置作为结尾的最长链长度，我们最终可以遍历找到全局最长的链。 步骤3：状态转移方程 基础情况：对于每个位置i，最短的链就是它自身，所以每个dp[ i ]至少为1。 如何推导dp[ i]？对于当前的i，我们需要看看在它之前（即索引j < i）的元素中，有哪些元素能够整除sortedNums[ i]（即sortedNums[ j] | sortedNums[ i]）。因为数组已经排序，所以j一定小于i，sortedNums[ j]一定小于sortedNums[ i]，整除关系只可能是sortedNums[ j]整除sortedNums[ i ]。 状态转移方程： dp[ i] = max( dp[ i], dp[ j] + 1 ) 对于所有满足 j < i 且 sortedNums[ i] % sortedNums[ j ] == 0 的 j。 解释：如果sortedNums[ j]能整除sortedNums[ i]，那么以sortedNums[ j]结尾的最长整除子集就可以把sortedNums[ i ]加在末尾，形成一个更长的子集。我们遍历所有满足条件的j，选择能使得新链最长的那个j。 步骤4：记录路径（重构解） 仅仅有dp数组只能知道最长子集的长度，但我们需要输出这个子集本身。因此，我们需要一个辅助数组prev[ i]来记录：在形成以i结尾的最长链时，链中i的前一个元素的索引是什么。如果没有前一个元素（即链长为1），则prev[ i ]可以设为-1或一个特殊值。 在状态转移时，如果我们在某个j处更新了dp[ i]（即dp[ i] = dp[ j] + 1），那么同时记录prev[ i ] = j。 步骤5：算法流程 如果输入数组nums为空，直接返回空集。 对nums进行排序得到sortedNums。 初始化两个数组： dp: 长度n（n为数组长度），初始值全为1（因为每个元素本身就是一个长度为1的整除子集）。 prev: 长度n，初始值全为-1（表示目前每个元素都是链的起点）。 初始化maxLen = 1（记录全局最长链长度），maxIndex = 0（记录全局最长链的末尾元素索引）。 循环遍历i从1到n-1（因为i=0是第一个元素，前面没有元素，dp[ 0 ]就是1）： 内层循环j从0到i-1： 检查sortedNums[ i] % sortedNums[ j ] == 0 是否成立。 如果成立，且dp[ j] + 1 > dp[ i ]，则： 更新dp[ i] = dp[ j ] + 1 记录prev[ i ] = j 在更新完dp[ i]后，检查如果dp[ i] > maxLen，则更新maxLen = dp[ i ] 和 maxIndex = i。 通过prev数组重构最长整除子集： 从maxIndex开始，根据prev数组不断向前回溯，将遇到的元素加入结果集。由于我们是向后（从链尾向链头）回溯，而我们需要的是正向的链，所以最后需要将结果反转。 具体操作：初始化一个空列表result。设置currentIndex = maxIndex。只要currentIndex != -1，就将sortedNums[ currentIndex]加入result，然后令currentIndex = prev[ currentIndex ]。最后将result反转后返回。 步骤6：复杂度分析 时间复杂度：O(n²)，因为有两层循环。排序的时间复杂度是O(n log n)，小于O(n²)，所以总时间复杂度是O(n²)。 空间复杂度：O(n)，用于存储dp和prev数组。 举例说明 以nums = [ 1, 2, 4, 8 ]为例： 排序后sortedNums = [ 1, 2, 4, 8 ]。 初始化dp = [ 1, 1, 1, 1], prev = [ -1, -1, -1, -1 ]。 遍历过程： i=1 (元素2): 检查j=0 (元素1): 2%1==0, 所以dp[ 1] = max(1, dp[ 0]+1=2) = 2, prev[ 1 ]=0。 i=2 (元素4): j=0: 4%1==0, dp[ 2] = max(1, 1+1=2) = 2, prev[ 2 ]=0。 j=1: 4%2==0, 且dp[ 1]+1=3 > 当前dp[ 2]=2, 所以dp[ 2]=3, prev[ 2 ]=1。 i=3 (元素8): j=0: 8%1==0, dp[ 3]=2, prev[ 3 ]=0。 j=1: 8%2==0, dp[ 3]=max(2, dp[ 1]+1=3)=3, prev[ 3 ]=1。 j=2: 8%4==0, dp[ 3]=max(3, dp[ 2]+1=4)=4, prev[ 3 ]=2。 最终maxLen=4, maxIndex=3。 回溯：从index=3(元素8)开始，prev[ 3]=2(元素4), prev[ 2]=1(元素2), prev[ 1]=0(元素1), prev[ 0]=-1停止。按回溯顺序得到[ 8,4,2,1]，反转后为[ 1,2,4,8 ]，即为答案。 这个算法通过排序将问题转化为寻找最长整除链，然后使用动态规划高效地解决了问题。