# C++ DP solution

• ``````vector<int> largestDivisibleSubset(vector<int>& nums) {
if (nums.empty())
return vector<int>();
sort(nums.begin(), nums.end());
vector<int> memo(nums.size(), 1);
int maxDivisibleSubsetSize = 1, largestElementIdx = 0;
// memo[i] represents the size of the max divisible subset whose largest element is nums[i]
for (int i = 1; i < nums.size(); i++) {
for (int j = i - 1; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {
memo[i] = max(memo[i], memo[j] + 1);
if (memo[i] > maxDivisibleSubsetSize) {
maxDivisibleSubsetSize = memo[i];
largestElementIdx = i;
}
}
}
}
// reconstruct the max divisible subset from memo
// We can deduct an element nums[i] is in the max subset if
// it can divide the element we just added to the max subset (the smallest element currently in the subset)
// and memo[i] is exactly 1 less than memo[prevIdx], meaning memo[prevIdx] was incremented because of nums[i]
vector<int> maxDivisibleSubset;
maxDivisibleSubset.push_back(nums[largestElementIdx]);
int prevIdx = largestElementIdx;
for (int i = largestElementIdx - 1; i >= 0; i--) {
if (maxDivisibleSubset.back() % nums[i] == 0 && memo[i] == memo[prevIdx] - 1) {
maxDivisibleSubset.push_back(nums[i]);
prevIdx = i;
}
}
return maxDivisibleSubset;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.