[C++ solution] O(n^2) solution similar to LIS with complete explanation
This question is similar to Longest Increasing Subsequence! The catch here is: if a num1 divides num2, then all the factors of num1 will also divide num2. Keepi
This question is similar to Longest Increasing Subsequence! The catch here is: if a num1 divides num2, then all the factors of num1 will also divide num2. Keeping this in mind, you can sort the array, and according simulate the LIS algorithm. \n\nBut later, you also have to present the elements of the divisible subset. For that, maintain a parent array and using it, trace back the whole subset! \n\nBelow is an implementation of the mentioned approach:\n```\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        int n=nums.size();\n        if(n==1) return {nums[0]};\n        sort(nums.begin(),nums.end());\n        vector<int> ans, parent(n,-1),dp(n,1);\n        \n        for(int i=0;i<n;i++) parent[i]=i;\n        int max_sub=0, idx=0;\n        \n        for(int i=1;i<n;i++)\n        {\n            for(int j=0;j<i;j++)\n            {\n                if(nums[i]%nums[j]==0) \n                {\n                    if(dp[i]<dp[j]+1)\n                    {\n                        parent[i]=j;\n                        dp[i]=dp[j]+1;\n                    }\n                }\n            }\n            \n            if(max_sub<dp[i]) max_sub=dp[i], idx=i;\n        }\n        \n        int k=idx;\n        \n        while(parent[k]!=k)\n        {\n            ans.push_back(nums[k]);\n            k=parent[k];\n        }\n        \n        ans.push_back(nums[k]);\n        return ans;\n        \n        \n    }\n};\n```
[]