# C++ Solution using DP

• ``````class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result(nums.size());
vector<int> ret;
for (int i = 0;i < nums.size();++i) {
for (int j = 0;j < i;++j) {
if (nums[i] % nums[j] == 0 && result[j].size() > result[i].size()) {
result[i] = result[j];
}
}
result[i].push_back(nums[i]);
if (ret.size() < result[i].size()) ret = result[i];
}
return ret;
}
};
``````

The total runtime is O(n^2). If any more efficient algorithm, welcome to discuss.

• Clean solution and easy to read.

• Considering you copy the vector in the loop, it's larger than O(n^2) if the array is long.

I adjust the code a little bit to avoid copying vectors:
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int> ptr(nums.size());
vector<int> length(nums.size());
vector<int> ret;

``````    int maxLength = -1;

for (int i = 0;i < nums.size();++i) {
ptr[i] = -1;
length[i] = 1;
for (int j = 0;j < i;++j) {
if (nums[i] % nums[j] == 0 && length[j] + 1 > length[i]) {
ptr[i] = j;
length[i] = length[j] + 1;
}
}
if (maxLength < length[i]) {
maxLength = length[i];
}
}