LeetCode Largest Divisible Subset Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine. Example 1:
nums: [1,2,3] Result: [1,2] (of course, [1,3] will also be ok)Example 2:
nums: [1,2,4,8] Result: [1,2,4,8]
给定一个数组，求满足这样一个条件的最大子集：该子集中的任意两个元素a和b满足a%b==0或者b%a==0。通过样例能够很好的理解这个题意。 这题的解法和最长上升子序列的求法很类似，用DP求解。首先对数组从小到大排序，然后对于第i个数nums[i]，定义dp[i]表示包含nums[i]、满足divisible subset条件、且nums[i]在该子集中是最大元素的子集的最大元素个数。其实就是把dp[i]直观的理解为以nums[i]结尾的满足divisible subset条件的最大子集合的大小。 求解dp[i]的递归方法是，遍历比nums[i]小的所有数nums[j]，如果nums[i]%nums[j]，则说明nums[i]可以扔到nums[j]所在的子集合中，所以dp[i]=dp[j]+1。遍历所有的j，找一个最大的dp[i]。 因为本题要输出具体的解，所以还定义一个数组parent[i]表示dp[i]的最大值是从哪个j来的。最后输出最优解的时候，j不断的递归往前找即可。 完整代码如下： [cpp] class Solution { public: vector<int> largestDivisibleSubset(vector<int>& nums) { if (nums.empty())return{}; sort(nums.begin(), nums.end()); int n = nums.size(), maxLen = 0, maxIdx = 0; vector<int> dp(n, 1), parent(n, -1); for (int i = 0; i < n; ++i) { for (int j = i – 1; j >= 0; –j) { if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; parent[i] = j; } } if (dp[i] > maxLen) { maxLen = dp[i]; maxIdx = i; } } vector<int> ans; while (maxIdx != -1) { ans.push_back(nums[maxIdx]); maxIdx = parent[maxIdx]; } return ans; } }; [/cpp] 本代码提交AC，用时39MS。 参考：https://www.hrwhisper.me/leetcode-largest-divisible-subset/]]>