Leetcode 368. 最大整除子集

题目

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。

测试样例

示例 1:

输入: [1,2,3] 输出: [1,2] (当然, [1,3] 也正确)

示例 2:

输入: [1,2,4,8] 输出: [1,2,4,8]

题解

动态规划 整除其实具有传递的性质，就比如[1,2,4,8],8%4 == 0，4%2 == 0，那么8%2==0。也就是说大数能整除一个数a，这个数a能整除b，那么大数就一定能整除b。所有我们先对数组进行升序排列 我们令dp[i]表示最大的整除子集的个数，对于nums[i]，如果nums[i]%nums[j] == 0，其中j<i，那么dp[i] = max(dp[i],dp[j]+1)。但题目并不是问的最大整除子集的个数，而是最大整除子集。因此我们还需要一个数组，记录每个变量与那个变量进行组合的，通过路径逆序查找。详细过程见代码

代码

vector<int> largestDivisibleSubset(vector<int>& nums) { if(nums.empty()) return {}; sort(nums.begin(),nums.end()); int n = nums.size(); vector<int> dp(n,1),path(n,-1); int max_index=0,max_length=1; for(int i=1; i<n; i++){ for(int j=i-1; j>=0; j--){ if(nums[i]%nums[j]==0 && dp[i]<dp[j]+1){ dp[i] = dp[j]+1; path[i] = j; //更新i结点的上一个结点，其与nums[j]结合 } } if(dp[i] > max_length){ //大于最大长度时，记录长度和下标 max_index = i; max_length = dp[i]; } } vector<int> ans; while(max_index != -1){ //逆序查找路径元素 ans.push_back(nums[max_index]); max_index = path[max_index]; } return ans; }

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/largest-divisible-subset 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。