largestDivisibleSubset.txt

368. Largest Divisible Subset

Given a set of distinct positive integers nums, return the largest subset answer such that
every pair (answer[i], answer[j]) of elements in this subset satisfies:

answer[i] % answer[j] == 0, or
answer[j] % answer[i] == 0
If there are multiple solutions, return any of them.

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n=nums.size();
        vector<int> index(n , -1) , dp(n+1 , 1);
        sort(nums.begin() , nums.end());
        int max_len=1;
        int idx=0;  
        for(int i=1;i<n;i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(nums[i]%nums[j]==0)
                {
                    if(dp[i]<1+dp[j])
                    {
                        dp[i]=1+dp[j];
                        index[i]=j;                
                        if(max_len<dp[i])
                        {
                            idx=i;
                            max_len=dp[i];
                        }
                    }
                }
            }
        }
        
        vector<int> res;
        int j=idx;
        while(j>=0)
        {
            res.push_back(nums[j]);
            j=index[j];
        }
        reverse(res.begin() , res.end());
        return res;
    }
};