Leetcode-最大整除子集（中等）

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

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

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

思路：
和最长递增子序列有点像，考虑动态规划来做。
dp[i]表示以nums[i]结尾的最长整除子集的长度。dp[i]=max(dp[j])+1; 其中j<i且nums[i]%nums[j]==0.
前提nums数组要从下到大排好序。
通过dp找到最长整除子集的大小后，保存此时的个数maxcount和此时的值maxvalue。
接下来，看怎么样把子序列提取出来。
倒序遍历数组，如果dp[i]=maxcount且maxvalue%nums[i]整除，就添加进ans。每次找到一个，maxcount减一，maxvalue要实时更新。

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(),nums.end());//先从小到大排序
        vector<int> dp(nums.size(),1);
        vector<int> ans;
        int maxcount=1,maxvalue=nums[0];
        for(int i=1;i<nums.size();i++){
            for(int j=i-1;j>=0;j--){
                if(nums[i]%nums[j]==0)
                    dp[i]=max(dp[i],dp[j]+1);
            }
            if(dp[i]>maxcount)//dp找到最大整除子集的长度和最后一个值
                maxcount=dp[i],maxvalue=nums[i];
        }
        for(int i=nums.size()-1;i>=0&&maxcount>0;i--){
            if(dp[i]==maxcount&&maxvalue%nums[i]==0){
                ans.push_back(nums[i]);
                maxvalue=nums[i];//maxvalue要更新！！！！重要：否则可能会有4 9 36的情况出现
                maxcount--;
            }              
        }
        return ans;//直接输出即可，ans内元素不要求顺序
    }
};