368. 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]

S: math & DP O(n^2)

对于已有的subset，任意比subset最大元素A大的数能进入subset的条件是能够整除A （比subset小的元素能进入的条件是能被最小的数整除）

将数组排序从前往后插入可以保证插入的都是比subset最大元素大的数字 （这里也可以从后往前）

dp[i]存储以nums[i]为结尾(最大元素)的最大subset的长度

dp元素初始化为1即每个subset只有自己一个元素

转移方程：对于j < i 若nums[i] % nums[j] == 0 dp[i] = dp[j] + 1

用trace数组追踪subset里元素的index, trace[i]表示以nums[i]结尾的subset中nums[i]的前一个元素的index, 若为-1则没有前一元素

    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return nums;
        sort(nums.begin(), nums.end());
        vector<int> dp(n, 1);
        vector<int> trace(n, -1); //用来追踪subset里的index序列
        int maxLen = 1, idx = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    trace[i] = j;
                    if (dp[i] > maxLen) {
                        maxLen = dp[i];
                        idx = i;
                    }
                }

            }
        }
        vector<int> result;
        while (idx >= 0) {
            result.push_back(nums[idx]);
            idx = trace[idx];
        }
        return result;
    }