Easy Beats 100%  || CPP || 8ms
Intuition\nGood problem, iconic for dp, lets say sorting will solve the problem by only comparing to prev index as small/large can\'t be 0 remainder. So use sam
# Intuition\nGood problem, iconic for dp, lets say sorting will solve the problem by only comparing to prev index as small/large can\'t be 0 remainder. So use same principle as LIS.\n# Approach\n1. Sort\n2. Take 2 for loops\n3. Second one will traverse from i-1 to 0\n4. Add the dp length if cond. satisfy \n5. Also add the prev index where u get that value from\n5. Update the maximum index for each i\n6. Then start from that index \n7. Go to prev index and add it\n8. Return ans\n\n# Complexity\n- Time complexity:\nO(n^2)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) \n    {   sort(nums.begin(),nums.end());\n        int index=0;\n        int n=nums.size();\n        vector<int>dp(n,1);\n        vector<int>prev(n,-1);\n        for(int i=0;i<n;i++){\n            for(int j=i-1;j>=0;j--){\n                if(nums[i]%nums[j]==0 && dp[i]<dp[j]+1){\n                    dp[i]=dp[j]+1;\n                    prev[i]=j;\n                }\n            }\n            if(dp[i]>dp[index]) index=i;  \n        }\n        vector<int>ans;\n        while(index>=0){\n            ans.push_back(nums[index]);\n            index=prev[index];\n        }\n        return ans;\n    }\n};\n```\n![upvote.jpeg](https://assets.leetcode.com/users/images/fc688158-c693-423e-84f2-cdb215322876_1707471861.119582.jpeg)\n
['C++']