和最长子序列类似。注意这里不仅要求出最长的长度，还要推出它的集合。

const int N = 1010;

class Solution {
public:

    int dp[N];   //记录长度

    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());

        int k = 0; //记录进入数组的数字下标
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] % nums[j] == 0){
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            if(dp[k] < dp[i]) k = i;
        }

        //求出了最长长度，现在要倒推出整除子集.当前k是最大子集的最后一个下标
        vector<int> ans;
        while(true){
            ans.push_back(nums[k]);
            if(dp[k] == 1) break;   //只有一个因子
            for(int j = 0; j < k; j++){
                if(nums[k] % nums[j] == 0 && dp[k] == dp[j] + 1){
                    k = j;
                    break;
                }
            }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};