C++ solution with direct thought


  • 0
    S
    class Solution {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums) {
            int s=nums.size();
            if(s<2) {return nums;}
            sort(nums.begin(),nums.end());
            vector<int> dp(s);
            vector<vector<int>> res(s);
            dp[0]=1;
            for(int i=0;i<s;i++) {
                vector<int> tmpres;
                    int tt=0;
                    int inde=-1;
                for(int j=i-1;j>=0;j--) {
                    if(nums[i]%nums[j]==0&&res[j].size()>tt) {
                        tt=res[j].size();
                        inde=j;
                    }
                }
                if(inde>-1) {
                    tmpres.insert(tmpres.end(),res[inde].begin(),res[inde].end());
                }
                tmpres.push_back(nums[i]);
                res[i]=tmpres;
            }
            int mv=0;
            int indd=0;
            for(int i=0;i<s;i++) {
                if(mv<res[i].size()) {
                    mv=res[i].size();
                    indd=i;
                }
            }
            return res[indd];
        }
    };
    

Log in to reply
 

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