368-largest-divisible-subset.md

368. Largest Divisible Subset - 最大整除子集

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (S_i，S_j) 都要满足：S_i % S_j = 0 或 S_j % S_i = 0。

如果有多个目标子集，返回其中任何一个均可。

 

示例 1:

输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)

示例 2:

输入: [1,2,4,8]
输出: [1,2,4,8]

---

题目标签：Math / Dynamic Programming

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	28 ms	897 KB

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        vector<int> res;
        sort(nums.begin(), nums.end());
        int size = nums.size();
        // corner case
        if (size == 0) {
            return res;
        }
        // longest subset's length endswith current element
        vector<int> dp(size, 1);
        // for the subset endswith current element, the index of previous element
        // we can get solution subset from this list
        vector<int> path(size, -1);
        // last element's index of current longest subset
        int ans = 0;
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    path[i] = j;
                }
            }
            if (dp[i] > dp[ans]) {
                ans = i;
            }
        }

        // get solution subset 
        for (int i = ans; i != -1; i = path[i]) {
            res.push_back(nums[i]);
        }
        return res;
    }
};
static auto _ = [](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();