LeetCode 第368题：最大整除子集

📖 文章摘要

本文详细解析LeetCode第368题“最大整除子集”，这是一道动态规划问题。文章提供了基于动态规划的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升动态规划问题解决能力的读者。

核心知识点： 动态规划、排序、整除关系 难度等级： 中等 推荐人群： 具有基础算法知识，想要提升动态规划问题解决能力的程序员

题目描述

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

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

示例

示例 1：

输入：nums = [1,2,4,8]
输出：[8,4,2,1]
解释：答案集合 [8,4,2,1] 可以通过 8%4=0, 4%2=0, 2%1=0 得到。

示例 2：

输入：nums = [1,2,3,4,6,8]
输出：[8,4,2,1]
解释：答案集合 [8,4,2,1] 可以通过 8%4=0, 4%2=0, 2%1=0 得到。

提示

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2 * 10^9
• nums 中的所有整数互不相同

解题思路

本题可以使用动态规划解决：

1. 对数组进行排序
2. 使用dp数组记录以每个数结尾的最大整除子集大小
3. 使用prev数组记录每个数的前一个数
4. 找到最大子集的最后一个数
5. 根据prev数组重建结果

时间复杂度： O(n^2) 空间复杂度： O(n)

🎯 算法流程演示

图解思路

动态规划过程

步骤	当前数	dp值	prev值	说明
1	1	1	-1	初始状态
2	2	2	1	2能被1整除
3	4	3	2	4能被2整除
4	8	4	4	8能被4整除

结果重建

步骤	当前数	前一个数	结果
1	8	4	[8]
2	4	2	[8,4]
3	2	1	[8,4,2]
4	1	-1	[8,4,2,1]

代码实现

C# 实现

public class Solution {
    public IList<int> LargestDivisibleSubset(int[] nums) {
        int n = nums.Length;
        if (n == 0) return new List<int>();
    
        Array.Sort(nums);
    
        int[] dp = new int[n];
        int[] prev = new int[n];
        Array.Fill(dp, 1);
        Array.Fill(prev, -1);
    
        int maxSize = 1;
        int maxIndex = 0;
    
        for (int i = 1; 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] > maxSize) {
                maxSize = dp[i];
                maxIndex = i;
            }
        }
    
        var result = new List<int>();
        while (maxIndex != -1) {
            result.Add(nums[maxIndex]);
            maxIndex = prev[maxIndex];
        }
    
        return result;
    }
}

Python 实现

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        n = len(nums)
        if n == 0:
            return []
        
        nums.sort()
    
        dp = [1] * n
        prev = [-1] * n
    
        max_size = 1
        max_index = 0
    
        for i in range(1, 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_size:
                max_size = dp[i]
                max_index = i
            
        result = []
        while max_index != -1:
            result.append(nums[max_index])
            max_index = prev[max_index]
        
        return result

C++ 实现

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return {};
    
        sort(nums.begin(), nums.end());
    
        vector<int> dp(n, 1);
        vector<int> prev(n, -1);
    
        int maxSize = 1;
        int maxIndex = 0;
    
        for (int i = 1; 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] > maxSize) {
                maxSize = dp[i];
                maxIndex = i;
            }
        }
    
        vector<int> result;
        while (maxIndex != -1) {
            result.push_back(nums[maxIndex]);
            maxIndex = prev[maxIndex];
        }
    
        return result;
    }
};

执行结果

C# 实现

• 执行用时：92 ms
• 内存消耗：24.8 MB

Python 实现

• 执行用时：28 ms
• 内存消耗：14.2 MB

C++ 实现

• 执行用时：4 ms
• 内存消耗：8.4 MB

性能对比

语言	执行用时	内存消耗	特点
C++	4 ms	8.4 MB	执行效率最高，内存占用最小
Python	28 ms	14.2 MB	代码简洁，内存占用适中
C#	92 ms	24.8 MB	类型安全，内存占用较大

代码亮点

1. 🎯 使用动态规划记录状态
2. 💡 使用prev数组记录路径
3. 🔍 处理空数组情况
4. 🎨 代码结构清晰，易于维护

常见错误分析

1. 🚫 未对数组排序
2. 🚫 未处理空数组
3. 🚫 状态转移错误
4. 🚫 结果重建错误

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
动态规划	O(n^2)	O(n)	高效，实现简单	需要额外空间
回溯	O(2^n)	O(n)	直观，易于理解	时间复杂度高

相关题目

• LeetCode 300. 最长递增子序列 - 中等
• LeetCode 673. 最长递增子序列的个数 - 中等
• LeetCode 354. 俄罗斯套娃信封问题 - 困难

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第368题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！