Share my C++ solution with some explanations


  • 0
    V

    Sort the set of distinct positive integers in descending order
    if i < j < k, and nums[i] % nums[j] ==0, and nums[j] % nums[k] == 0, then there must be nums[i] % nums[k] == 0, that is why we need do sorting
    dp[i] = max (dp[i], dp[j] + 1), 0 <= j < i && nums[j] % nums[i] == 0

    class Solution {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums) {
            vector<int> ret;
            int n = nums.size();
            if (n == 0)
                return ret;
            
            sort(nums.begin(), nums.end(), greater<int>());
            
            vector<int> dp(n, 1);
            vector<int> path(n, 0);
            int max_len = 1;
            int start = 0;
            
            for (int i = 0; i < n; i++)
                path[i] = i;
            
            for (int i = 1; i < n; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (nums[j] % nums[i] == 0)
                    {
                        if (dp[i] < dp[j] + 1)
                        {
                            dp[i] = dp[j] + 1;
                            path[i] = j;
                            
                            if (max_len < dp[i])
                            {
                                max_len = dp[i];
                                start = i;
                            }
                        }
                    }
                }
            }
            
            while (path[start] != start)
            {
                ret.push_back(nums[start]);
                start = path[start];
            }
            ret.push_back(nums[start]);
            
            return ret;
        }
    };
    

Log in to reply
 

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