美文网首页
Largest Divisible Subset

Largest Divisible Subset

作者: 我叫胆小我喜欢小心 | 来源:发表于2017-05-05 09:37 被阅读18次

    题目来源
    求最大的可整除子集,就是子集中任意一对元素都是倍数关系。
    我主要利用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;
        }
    };
    

    相关文章

      网友评论

          本文标题:Largest Divisible Subset

          本文链接:https://www.haomeiwen.com/subject/yryjtxtx.html