Easy DP with path record, C++ code, O(n^2) time on worst case, O(n) space
the idea is using a bucket to record which nums can be the current longest sequence,\nand meantime using pair record the pre-num's id in its bucket, so we can g
the idea is using a bucket to record which nums can be the current longest sequence,\nand meantime using pair record the pre-num's id in its bucket, so we can get the result using it.\n\nsee this case [1,2,3,4,5,6,7,24]\n\nat last it runs like this:\n\n     1 | 2 | 4 | 24\n       | 3 | 6 |\n       | 5 |    \n       | 7 |    \ncode:\n\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        vector<int> ret;\n        int n = nums.size();\n        if (!n) return ret;\n        sort(nums.begin(), nums.end());\n        vector<pair<int, int>> dp[n];\n        int maxi = 0;\n        dp[maxi].push_back(make_pair(nums[0], -1));\n        for (int i = 1; i < n; ++i) {\n            int j = maxi;\n            while (j >= 0) {\n                for (int id = 0; id < dp[j].size(); ++id) {\n                    if (nums[i] % dp[j][id].first == 0) {\n                        dp[j + 1].emplace_back(nums[i], id);\n                        maxi = max(maxi, j + 1);\n                        goto out_of_while;\n                    }\n                }\n                --j;\n            }\n            dp[j + 1].emplace_back(nums[i], -1);\n            out_of_while:;\n        }\n        int i = maxi, id = 0;\n        while (i >= 0) {\n            ret.push_back(dp[i][id].first);\n            id = dp[i][id].second;\n            --i;\n        }\n        return ret;\n    }
[]