本文主要是介绍最大整除子集——动态规划与数学原理结合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给出一个由无重复的正整数组成的集合, 找出其中最大的整除子集, 子集中任意一对 (Si, Sj) 都要满足: Si % Sj = 0 或 Sj % Si = 0。
如果有多个目标子集，返回其中任何一个均可。
示例 1:
集合: [1,2,3]
结果: [1,2] (当然, [1,3] 也正确)
直觉告诉我先排个序是很稳的，但是一般动态规划都是计算什么解的长度，解的最大最小值之类的，突然要返回一个解，还真不会做了。
但是实际上这题动态规划思想非常简单：
排序后，dp【i】是第i个数字结尾的数组段所能拥有的最大整数子集长度。
很显然，dp【i】=max（dp【a1】，dp【a2】。。。dp【ak】）+1，其中dp【ax】代表能实现dp【i】%dp【ax】==0，
也就是说dp【i】是所有在i前面的数字能构造最大整除子集的最长的再加1.
我的思路基本上和上一致，
使用动态规划找到最大的子集数，再通过ind数组来依次找到他的前面一个因子：
比如我已经找到了【1，2，4，8，16，17】的最大子集数是5，且最大数是16，ind数组为【-1,0,1,2,3,-1】,ind数组就是他的最长子集最大因子
代码如下：
class Solution {
public:vector<int> largestDivisibleSubset(vector<int>& nums) {vector<int> a,res,ind;if(nums.size()==0)return res;sort(nums.begin(),nums.end());for (int i=0;i<nums.size();i++){int la=0,index=-1;for (int j=0;j<i;j++)if(nums[i]%nums[j]==0){if(la<=a[j])index=j;la=(la>a[j])?la:a[j];}ind.push_back(index);la=la+1;a.push_back(la);}//找到最大的子集数及其索引int k=-1,index=-1;for (int i=0;i<a.size();i++){if(k<=a[i]){index=i;k=a[i];}}while(index!=-1){res.push_back(nums[index]);index=ind[index];} return res;}
};
这篇关于最大整除子集——动态规划与数学原理结合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
