1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
const int n = nums.size();
sort(begin(nums), end(nums));
vector<int> dp(n, 1);
int maxVal = dp[0], maxSize = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j)
if (nums[i] % nums[j] == 0)
dp[i] = max(dp[i], dp[j] + 1);
if (dp[i] > maxSize) {
maxSize = dp[i];
maxVal = nums[i];
}
}
if (maxSize == 1)
return {nums[0]};
vector<int> ans;
for (int i = n - 1; maxSize > 0; --i)
if (dp[i] == maxSize && maxVal % nums[i] == 0) {
--maxSize;
maxVal = nums[i];
ans.emplace_back(nums[i]);
}
return ans;
}
};
|