1.题目基本信息

1.1.题目描述

给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：

• answer[i] % answer[j] == 0 ，或

• answer[j] % answer[i] == 0

如果存在多个有效解子集，返回其中任何一个均可。

1.2.题目地址

https://leetcode.cn/problems/largest-divisible-subset/description/

2.解题方法

2.1.解题思路

动态规划

2.2.解题步骤

第一步，预处理。将nums进行升序排列。并构建维护变量，使用prevs维护以nums[i]结尾的最长可整除子序列的前一个元素的索引；使用maxI维护最长序列的结尾索引

第二步，状态定义。dp[i]维护以nums[i]结尾的最长可整除序列的长度

第三步，状态初始化。默认都设置为0，为了后续的遍历更新机制

第四步，状态转移。dp[i]=max(dp[j] for j in range(i) if nums[i]%nums[j]==0)+1；并在转移过程中更新prevs和maxI

第五步，根据prevs和maxI逆向构建出合法子序列，并进行返回

3.解题代码

python代码

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        # 思路：动态规划
        # 参考：Leetcode 300. 最长递增子序列
        # 第一步，预处理。将nums进行升序排列。并构建维护变量，使用prevs维护以nums[i]结尾的最长可整除子序列的前一个元素的索引；使用maxI维护最长序列的结尾索引
        n = len(nums)
        nums.sort()
        prevs = [-1] * n
        maxI = 0
        # 第二步，状态定义。dp[i]维护以nums[i]结尾的最长可整除序列的长度
        dp = [0] * n
        # 第三步，状态初始化。默认都设置为0，为了后续的遍历更新机制
        # 第四步，状态转移。dp[i]=max(dp[j] for j in range(i) if nums[i]%nums[j]==0)+1；并在转移过程中更新prevs和maxI
        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[j] > dp[i]:
                    dp[i] = dp[j]   # 这里让dp[i]成为max(dp[j] for j in range(i))
                    prevs[i] = j
            dp[i] += 1
            if dp[i] > dp[maxI]:
                maxI = i
        # 第五步，根据prevs和maxI逆向构建出合法子序列，并进行返回
        # print(prevs, maxI)
        result = []
        b = maxI
        while b != -1:
            result.append(nums[b])
            b = prevs[b]
        # print(result)
        return result[::-1]

4.执行结果