[C++] Easy to Understand- Bottom Up DP Similar to LIS
class Solution {\npublic:\n\n    vector largestDivisibleSubset(vector& nums) {\n     if(nums.size()<=1) return nums;\n     sort(nums.begin(),nums.end());\n     
class Solution {\npublic:\n\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n     if(nums.size()<=1) return nums;\n     sort(nums.begin(),nums.end());\n     vector<int>parent(nums.size(),-1);//To store the  parent index of current element. So we can trace back to the subset\n     vector<int>dp(nums.size(),1);\n     int maxlength=0;int pos=0;\n     //Similar to LIS\n     for(int i=1;i<nums.size();i++)\n     {\n         for(int j=0;j<i;j++)\n         {\n             if(nums[i]%nums[j]==0) dp[i]=max(dp[i],1+dp[j]);\n             if(dp[i]==1+dp[j]) parent[i]=j;//means j is parent of i \n         }\n         if(dp[i]>maxlength)\n         {\n             maxlength=dp[i];\n             pos=i;\n         }\n     }\n     vector<int>result(maxlength);\n     for(int i=maxlength-1;i>=0;i--)\n     {\n         result[i]=nums[pos];\n         pos=parent[pos];\n     }\n    return result;\n    }\n    };
[]