C++ dp


  • 0
    class Solution {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums) {
            if(nums.empty()) return {};
            int len = nums.size();
            sort(nums.begin(),nums.end());
            int dp[len];
            vector<vector<int>> group(len);
            for(int i=0;i<len;i++) {
                dp[i] = 1;
            }
            group[0].push_back(nums[0]);
            for(int i=1;i<len;i++) {
                for(int j=i-1;j>=0;j--) {
                    if(nums[i]%nums[j]==0) {
                        if(dp[j]+1>dp[i]) {
                            dp[i] = dp[j]+1;
                            group[i] = group[j];
                        }
                    }
                }
                group[i].push_back(nums[i]);
            }
            int m = 0, idx = 0;
            for(int i=0;i<len;i++) {
                if(dp[i]>m) {
                    idx = i;
                    m = dp[i];
                }
            }
            return group[idx];
        }
    };
    

Log in to reply
 

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