关键词：

【LetMeFly】368.最大整除子集

力扣题目链接：https://leetcode.cn/problems/largest-divisible-subset/

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

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

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

 

示例 1：

输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

示例 2：

输入：nums = [1,2,4,8]
输出：[1,2,4,8]

 

提示：

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

方法一：动态规划 + traceback

上来先给nums从小到大排个序，这没什么好说的。

排完序后：

step1. 动态规划求得以nums[i]结尾的最长“递增倍数串”的长度

数组中各个元素各不相同，想要“互为倍数”，就要“大的 是 小的 的 整数倍”

假如一个“互为倍数”数组中已经有了两个元素5, 15，那么想要往这个数组中再添加一个元素的话，新的元素就要是15的整数倍。这是因为我们“上来就给nums从小到大排了个序”。

如果一个数是15的整数倍，那么它一定是5的整数倍。

这不，动态规划的转移方程就来了？

$dp[i]=\max dp[i],dp[j]+1$，其中$j<i\wedge nums[i]\%nums[j]=0$

说人话就是，怎么求$dp[i]$呢？在所有的小于$i$的下标中，如果某个数能被$nums[i]$整除（假设为第$j$个数），那么$dp[i]=\max (dp[i],dp[j]+1)$

因为$nums[i]$是$nums[j]$的倍数的话，$num[i]$可以添加到以$nums[j]$结尾的“递增互为倍数集合”中。

这样，两层循环就能求出$dp$数组的值，其中$dp[i]$表示以$nums[i]$结尾的“递增互为倍数集合”的最大大小。

vector<int> dp(n, 1);
for (int i = 0; i < n; i++) 
    for (int j = 0; j < i; j++) 
        if (nums[i] % nums[j] == 0) 
            dp[i] = max(dp[i], dp[j] + 1);
        
    

step2. 根据“递增倍数串”后面的元素倒推出前面的元素

题目问的不是“互为倍数集合的最大元素个数”，而是要你把这个集合给出来。

但是这就不难了。我们在step1中动态规划求“最大大小”时，可以额外记录一下：

1. 最大大小是多少
2. 最大的集合中，最大的数有多大

只需要做如下更改：

vector<int> dp(n, 1);
int maxLength = 0;
int maxVal = 0;
for (int i = 0; i < n; i++) 
    for (int j = 0; j < i; j++) 
        if (nums[i] % nums[j] == 0) 
            dp[i] = max(dp[i], dp[j] + 1);
        
    
    if (dp[i] > maxLength) 
        maxLength = dp[i];
        maxVal = nums[i];
    

这样，我们就知道了“答案集合的最大数”、“答案集合的大小”

假如答案集合是[5, 15, 30]，那么我们知道的是：

1. 答案中的最大数是30
2. 答案集合的大小是3

同时我们也知道了整个dp数组，其中5对应的dp值是1，15对应的dp值是2，30对应的dp值是3

因此我们可以从后往前遍历一遍数组（从大到小）

如果遇到某个数对应的dp值恰好等于“maxLength”，并且这个数能被“maxVal”整除，那么就说明这个数是集合中的一个数

更新maxLength为maxLength - 1，更新maxVal为这个数。

vector<int> ans(maxLength);
for (int i = n - 1; i >= 0; i--) 
    if (maxVal % nums[i] == 0 && dp[i] == maxLength) 
        ans[--maxLength] = nums[i];
        maxVal = nums[i];
        if (!maxLength)
            break;
    

同样以答案集合[5, 15, 30]为例：

1. maxLength = 3, maxVal = 30，找到30时，发现30对应的dp值恰好为3，且30能被30整除。因此我们得到了答案集合中的30，并将maxLength更新为2，将maxVal更新为30
2. maxLength = 2, maxVal = 30，找到15时，发现15对应的dp值恰好为2，且30能被15整除。因此我们得到了答案集合中的15，并将maxLength更新为1，将maxVal更新为15
3. maxLength = 1, maxVal = 15，找到5时，发现15对应的dp值恰好为1，且15能被5整除。因此我们得到了答案集合中的5，并将maxLength更新为.，将maxVal更新为5

寻找结束。

• 时间复杂度$O(n^2)$，其中$n$是$nums$的大小
• 空间复杂度$O(n)$

AC代码

C++

class Solution 
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) 
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> dp(n, 1);
        int maxLength = 0;
        int maxVal = 0;
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < i; j++) 
                if (nums[i] % nums[j] == 0) 
                    dp[i] = max(dp[i], dp[j] + 1);
                
            
            if (dp[i] > maxLength) 
                maxLength = dp[i];
                maxVal = nums[i];
            
        
        vector<int> ans(maxLength);
        for (int i = n - 1; i >= 0; i--) 
            if (maxVal % nums[i] == 0 && dp[i] == maxLength) 
                ans[--maxLength] = nums[i];
                maxVal = nums[i];
                if (!maxLength)
                    break;
            
        
        return ans;
    
;

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127210616

368.最大整除子集（序列dp）(代码片段)

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

最大整除子集(代码片段)

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对(Si，Sj)都要满足：Si %Sj =0或Sj %Si =0。如果有多个目标子集，返回其中任何一个均可。 示例1:输入:[1,2,3]输出:[1,2](当然,[1,3]也... 查看详情

leetcode698划分为k个相等的子集[回溯剪枝]heroding的leetcode之路(代码片段)

解题思路：是一道比较困难的中等题，首先简单判断子集的和是否能够被k整除，能整除得到整除的数target，然后从大到小排序看最大的数是否小于target，否则返回false，这里从大到小排序很讲究，否则... 查看详情

leetcode中等1262可被三整除的最大和(代码片段)

给你一个整数数组nums，请你找出并返回能被三整除的元素最大和。示例1：输入：nums=[3,6,5,1,8]输出：18解释：选出数字3,6,1和8，它们的和是18（可被3整除的最大和）。示例2：输入：nums=... 查看详情

leetcode中等1262可被三整除的最大和(代码片段)

给你一个整数数组nums，请你找出并返回能被三整除的元素最大和。示例1：输入：nums=[3,6,5,1,8]输出：18解释：选出数字3,6,1和8，它们的和是18（可被3整除的最大和）。示例2：输入：nums=... 查看详情

leetcode1090.受标签影响的最大值(代码片段)

问题：我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。我们从这些项中选出一个子集 S，这样一来：|S|<=num_wanted对于任意的标签 L，子集 S 中标签为 L 的项的数目总满足&... 查看详情

leetcode2044.统计按位或能得到最大值的子集数目(代码片段)

...架代码如下：intcountMaxOrSubsets(int*nums,intn)3、原题链接LeetCode2044.统计按位或能得到最大值的子集数目二、解题报告1、思路分析  (1)(1)(1)对于一个nnn个元素的集合S=0,1,2,...,n−1S=\\0,1,2,...,n-1\\S=0,1,2,...,n−1，每个元... 查看详情

不能被 K 整除的两个和的最大子集

】不能被K整除的两个和的最大子集【英文标题】：MaximumsubsetwhichhasnosumoftwodivisiblebyK【发布时间】：2012-12-0917:05:41【问题描述】：给定集合1,2,3,...,N。我必须找到给定集合的子集的最大大小，以便子集中的任何2个数字的总和不能... 查看详情

[leetcode]78.子集(代码片段)

题目链接:https://leetcode-cn.com/problems/subsets/题目描述:给定一组不含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例:输入:nums=[1,2,3]输出:[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]思路:思... 查看详情

leetcode-滑动窗口极值搜索树后序遍历统计差值对划分相等子集(代码片段)

滑动窗口极值LeetCode：239.滑动窗口最大值改进：整数数组nums，长度为k的滑动窗口，滑动窗口每次向右移动一位。返回每个滑动窗口中的最小值，组成列表，时间复杂度O(N)classSolution:defmaxSlidingWindow(self,nums:List[int],k:int)- 查看详情

leetcode0474.一和零(代码片段)

【LetMeFly】474.一和零力扣题目链接：https://leetcode.cn/problems/ones-and-zeroes/给你一个二进制字符串数组strs和两个整数m和n。请你找出并返回strs的最大子集的长度，该子集中最多有m个0和n个1。如果x的所有元素也是y的元素，... 查看详情

leetcode（326）powerofthree(代码片段)

题目Givenaninteger,writeafunctiontodetermineifitisapowerofthree.分析本题判断给定一个整数是否为3的整次幂，不可用递归和循环。32bit表示的int，3的整次幂最大数为1162261467，所以只需判断给定整数n能否被该最大数整除即可。代码... 查看详情

leetcode474.一和零（01背包问题）(代码片段)

leetcode474.一和零2021/06/06每日一题https://leetcode-cn.com/problems/ones-and-zeroesleetcode2021/06/06每日一题https://leetcode-cn.com/problems/ones-and-zeroes一和零给你一个二进制字符串数组strs和两个整数m和n。请你找出并返回strs的最大子集的大小，该子... 查看详情

leetcode1979.找出数组的最大公约数（c++）(代码片段)

1979.找出数组的最大公约数1题目描述2示例描述2.1示例12.2示例22.3示例33解题提示4解题思路5代码详解1题目描述给你一个整数数组nums，返回数组中最大数和最小数的最大公约数。两个数的最大公约数是能够被两个数整除的最大... 查看详情

leetcode之1979.找出数组的最大公约数(代码片段)

题目题目描述给你一个整数数组nums，返回数组中最大数和最小数的最大公约数。两个数的最大公约数是能够被两个数整除的最大正整数。示例1：输入：nums=[2,5,6,9,10]输出：2解释：nums中最小的数是2nums中最... 查看详情

leetcode——子集1,2(代码片段)

1.子集（1）回溯参考全排列1，一样的方法classSolutionList<List<Integer>>result=newArrayList<>();//存放符合条件结果的集合Deque<Integer>path=newLinkedList<>();//用来存放符合条件结果p 查看详情

leetcode第302场周赛(代码片段)

LeetCode第302场周赛第302场周赛6120.数组能形成多少数对6164.数位和相等数对的最大和6121.裁剪数字后查询第K小的数字6122.使数组可以被整除的最少删除次数总结第302场周赛我走得很慢！但我从不后退！6120.数组能形成多少数... 查看详情

leetcode第302场周赛(代码片段)

LeetCode第302场周赛第302场周赛6120.数组能形成多少数对6164.数位和相等数对的最大和6121.裁剪数字后查询第K小的数字6122.使数组可以被整除的最少删除次数总结第302场周赛我走得很慢！但我从不后退！6120.数组能形成多少数... 查看详情