题目来源
求最大的可整除子集,就是子集中任意一对元素都是倍数关系。
我主要利用dp来记录最大值,然后利用pre来记录对应最大值的上一个元素。
代码如下:
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
sort(nums.begin(), nums.end());
int len = nums.size();
vector<int> res;
if (len == 0)
return res;
vector<int> dp(len, 1);
vector<int> pre(len, 0);
int curMax = 1, resMax = 0;
for (int i=1; i<len; i++) {
pre[i] = i;
for (int j=0; j<i; j++) {
if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
pre[i] = j;
}
}
if (dp[i] > curMax) {
curMax = dp[i];
resMax = i;
}
}
int cur = resMax;
for (int i=0; i<curMax; i++) {
res.push_back(nums[cur]);
cur = pre[cur];
}
return res;
}
};
网友评论