368 Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (S_i, S_j) of elements in this subset satisfies: S_i % S_j = 0 or S_j % S_i = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

<pre>
nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)
</pre>

Example 2:

<pre>
nums: [1,2,4,8]

Result: [1,2,4,8]
</pre>

解体思路

首先我们根据条件S_i % S_j = 0 or S_j % S_i = 0可以推出，最大可整除子集中任意两个数一定有一个数可以被可以另一个数整除。
也就是说，将这些数按从小到大的顺序排列，则后一个数一定可以被前一个数整除!
于是问题转换为了类似于最长不下降子序列的DP。

代码

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        
        int len = nums.size();
        int ans = 0, ansi;
        int dp[len];
        int pre[len];//用于保存最长可整除序列的路径
        for (int i=0;i<len;i++){
            dp[i] = 1;
            pre[i] = -1;
            for (int j=0;j<i;j++){
                if (nums[i]%nums[j] == 0 && dp[j]+1>dp[i]){
                    dp[i] = dp[j]+1; pre[i] = j;
                }
            }
            if (dp[i] > ans){
                ans = dp[i]; ansi = i;
            }
        }
        //找出最长可整除子序列，方法类似于最长不下降子序列
        vector<int> res;
        for (int i=1;i<=ans;i++){
            res.push_back(nums[ansi]); ansi = pre[ansi];
        }
        //利用pre数组找到最长可整除子序列
        sort(res.begin(),res.end());
        return res;
    }
};