c++ dp 43ms


  • 0
    T
    /*  Mine
        f[i]以i为尾最多的个数
        f[i]=max(f[j])+1 if f[i]%f[j]==0,j<i
        route[i]:f[i]是由谁更新来的
    */
    class Solution {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums)
        {
            vector<int> ans; 
            int len = nums.size();
            if (len == 0) return ans;
            int maxLen = 0, maxIndex = 0;
            vector<int> f(len,0);
            vector<int> route(len);
            sort(nums.begin(),nums.end());
            for(int i=0;i<len;i++) route[i]=i;
            f[0]=1;
            for(int i=1;i<len;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if (nums[i]%nums[j] == 0)
                    {
                        if (f[j]>f[i])
                        {
                            f[i]=f[j];
                            route[i]=j;
                        }
                    }
                }
                f[i]++;
                if(f[i]>maxLen)
                {
                    maxLen =  f[i];
                    maxIndex = i;
                }
            }
            while(route[maxIndex]!=maxIndex)
            {
                ans.push_back(nums[maxIndex]);
                maxIndex = route[maxIndex];
            }
            ans.push_back(nums[maxIndex]);
            sort(ans.begin(),ans.end());
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.