[C++] DP with comments
\nclass Solution { //Leetcode 368:  DP;\npublic:// Time/Space: O(N^2); O(N)\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(begin(num
```\nclass Solution { //Leetcode 368:  DP;\npublic:// Time/Space: O(N^2); O(N)\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(begin(nums), end(nums));\n        const int n = nums.size();\n        vector<int> dp(n), parent(n), res; //dp[i]: max size of desired subset beginning with nums[i];\n        int maxSize = 0;   // max size of the desired subset\n        int beginIdx = -1; // index of the smallest element in the sorted nums to build the set\n        for(int i = n - 1; i >=0; i--){\n            for(int j = i; j < n; j++){ // i <= j;  // Note1\n                if(nums[j] % nums[i] == 0 && dp[i] < dp[j] + 1){\n                    dp[i] = dp[j] + 1;\n                    parent[i] = j; // given that parent[i] is always updated with dp[i] together, \n                                   // these two  can be packed to make the code more compact                    \n                }                      \n            }\n            if(maxSize < dp[i]){\n                maxSize = dp[i]; // redudant, but self-explained\n                beginIdx= i;\n            }\n        }\n        \n        while(maxSize--){ //need collect #maxSize items \n            res.push_back(nums[beginIdx]);\n            beginIdx = parent[beginIdx];\n        }            \n        return res;\n    }\n};\n//Note1: corner case, we need begin with j=i so that we can include 1st item into the set\n```\n\nVersion 2:  In case you hate frequent collecting gobal maximal size, you can use max_element:\n```\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        if(nums.empty()) return {};\n        sort(begin(nums), end(nums));\n        const int n = nums.size();\n        vector<int> dp(n), parents(n), res;\n        int maxL = 0, beginIndex = -1;\n        for(int i = n - 1; i >= 0; i--)\n            for(int j = i; j < n; j++)\n                if(nums[j] % nums[i] == 0 && dp[i] < dp[j] + 1){\n                    dp[i] = dp[j] + 1;                    \n                    parents[i] = j;\n                }\n            \n        beginIndex = max_element(begin(dp),end(dp)) - begin(dp);\n        maxL = dp[beginIndex];\n        \n        while(maxL--){\n            res.push_back(nums[beginIndex]);\n            beginIndex= parents[beginIndex];\n        }\n        return res;\n    }\n};\n```
[]