Largest Divisible Subset

题目来源
求最大的可整除子集，就是子集中任意一对元素都是倍数关系。
我主要利用dp来记录最大值，然后利用pre来记录对应最大值的上一个元素。
代码如下：

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        vector<int> res;
        if (len == 0)
            return res;
        vector<int> dp(len, 1);
        vector<int> pre(len, 0);
        int curMax = 1, resMax = 0;
        for (int i=1; i<len; i++) {
            pre[i] = i;
            for (int j=0; j<i; j++) {
                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    pre[i] = j;
                }
            }
            if (dp[i] > curMax) {
                curMax = dp[i];
                resMax = i;
            }
        }
        int cur = resMax;
        for (int i=0; i<curMax; i++) {
            res.push_back(nums[cur]);
            cur = pre[cur];
        }
        return res;
    }
};