33.Divisible Set

vector<int> divisibleSet(vector<int> &arr)

{

    // Write your code here.

    int n=arr.size(),i,j;

    vector<int>ans;

    int par[n+5];

    for(i=0;i<=n;i++)par[i]=i;

    int dp[n+5];

    sort(arr.begin(),arr.end());

    for(i=0;i<=n;i++)

    {

        dp[i]=1;

    }

    for(i=0;i<n;i++)

    {

        for(j=0;j<i;j++)

        {

            if(arr[i]%arr[j]==0||arr[j]%arr[i]==0)

            {

                if(dp[i]<dp[j]+1)

                {

                    dp[i]=dp[j]+1;

                    par[i]=j;

                }

            }

        }

    }

    

     int pos=0;

     int mx=0;

     for(i=0;i<n;i++)

     {

            if(dp[i]>mx)

            {

                mx=dp[i];

                pos=i;

            }

     }

    // cout<<pos<<endl;

     ans.push_back(arr[pos]);

     while(par[pos]!=pos)

     {

         pos=par[pos];

         ans.push_back(arr[pos]);

     }

    return ans;

}