Largest Divisible Subset

 Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)

Example 2:

Input: [1,2,4,8]
Output: [1,2,4,8]

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if(nums.size()<=1)return nums;
        vector<int> v;
        int i=0,j=1;
        
        sort(nums.begin(),nums.end());
        if(nums.size()==2)
        {
         if(nums[0]%nums[1]==0||nums[1]%nums[0]==0){
                v.push_back(nums[0]);   
             v.push_back(nums[1]);
         }else{
              v.push_back(nums[0]);   
         }
             return v;
        }
        
                  
        int n=nums.size();
        
        int count[n];
        memset(count,0,sizeof(count));
        for(int i=1;i<nums.size();++i)
        {
            for(int j=i-1;j>=0;--j)
            {
                if(nums[i]%nums[j]==0)
                count[i]=max(count[i],count[j]+1);
                
            }
        }
        int maxInd=0;
        for(int i=1;i<n;++i)
        {
          maxInd= (count[i]>count[maxInd]) ? i:maxInd;
        }
        
        int maxcnt=count[maxInd];
        v.push_back(nums[maxInd]);
        --maxInd;
        --maxcnt;
        while(maxInd>=0)
        {
            if(v.back()%nums[maxInd]==0&&maxcnt==count[maxInd])
            {
                v.push_back(nums[maxInd]);
                --maxcnt;
            }
            --maxInd;
        }
        sort(v.begin(),v.end());
        return v;
    }
};