Similar to LIS vs topo sort O(n^2)||12 ms Beats 92.77%
Intuition\n Describe your first thoughts on how to solve this problem. \nUse a similar argument to LIS to solve the question.\n\nI don\'t see any tricks from Nu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse a similar argument to LIS to solve the question.\n\nI don\'t see any tricks from Number Theory, but Graph Theory is possible, to find the longest chain! \n\n2nd approach uses toplogoical sort, a graphical BFS approach which is relatively slow but accepted. ( 28ms Beats 63.07%)\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sort `nums`\n2. Initialize state arrays with `len(n, 1), prev(n, -1)`\n3. Use a nested loop to proceed the DP. If `nums[i] % nums[j] == 0 && len[i] < len[j] + 1` update len[i], prev[i]. If `len[i]>maxLen` update `maxLen, iMax`.\n4. Use `prev` to construct `ans` and return it\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n $$O(n^2)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n# C++ Code ||12 ms Beats 92.77%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    // similiar to LIS O(n^2) solution\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n        vector<int> len(n, 1), prev(n, -1);//state arrays\n\n        int maxLen=0, iMax= -1;\n        for (int i=0; i<n; i++) {\n            for (int j=i+1; j < n; j++) {\n                if (nums[j]%nums[i]==0 && len[j]<len[i]+1) {\n                    len[j]=len[i]+1;\n                    prev[j]=i;\n                }\n            }\n            if (len[i]>maxLen) {\n                maxLen=len[i];\n                iMax=i;\n            }\n        }\n        \n        vector<int> ans;\n        for (int j=iMax; j!=-1; j=prev[j]) {\n            ans.push_back(nums[j]);\n        }\n        return ans;\n    }\n};\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# C++ topological sort\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        int n = nums.size();\n        vector<int> deg(n, 0), prev(n, -1);\n        vector<vector<int>> adj(n);\n\n        for (int i = 0; i < n; i++) {//Build adjacent list\n            for (int j = i+1; j < n; j++) {\n                if (nums[j] % nums[i] == 0) {\n                    adj[i].push_back(j);\n                    deg[j]++;//indegree\n                }\n            }\n        }\n        // BSF\n        queue<int> q;\n        for (int i = 0; i < n; i++) {\n            if (deg[i]==0) q.push(i);\n        }\n\n        int iMax= 0;\n        while (!q.empty()) {\n            int x=q.front();\n            q.pop();\n            for (int y : adj[x]) {\n                if (--deg[y] == 0) {\n                    q.push(y);\n                    prev[y]=x;//assign prev\n                }\n            }\n            iMax=x;\n        }\n        vector<int> ans;\n        for (int j=iMax; j!=-1; j=prev[j]) {\n            ans.push_back(nums[j]);\n        }\n        return ans;\n    }\n};\n\n\n```
['Dynamic Programming', 'Breadth-First Search', 'Topological Sort', 'Sorting', 'C++']