The title comes from leetcode, Solutions and ideas represent only personal views . Portal .
difficulty ： secondary
Time ：-
tag： Sort 、 Dynamic programming

subject

Here you are No repetition A set of positive integers nums , Please find out and return the largest subset of them answer , Every element in a subset is a pair of (answer[i], answer[j]) All should be satisfied ：
answer[i] % answer[j] == 0 , or
answer[j] % answer[i] == 0
If there are multiple subsets of efficient solutions , Go back to any one of them .

Example 1：

 Input ：nums = [1,2,3]
 Output ：[1,2]
 explain ：[1,3]  It will also be seen as the right answer .

Example 2：

 Input ：nums = [1,2,4,8]
 Output ：[1,2,4,8]

Tips ：
1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 10⁹
nums All integers in Different from each other

Ideas

Dynamic programming

The first point ：
a % b == 0 or b % a == 0 Can be accepted , So if a > b
a % b May be 0, but b % a It must not be for 0

that , We will array 【 Sort 】 after , Just judge a（ A larger number ） Divide or not b（ Smaller numbers ） that will do .

Second point ：
if a % b == 0 && b % c==0 => a % c == 0

however a % c == 0 && b % c == 0 , Can't get a % b == 0

in other words ,% Yes 【 One way transitivity 】

In fact, this question is ok transformation It has become a topic we were very familiar with before 【 Longest ascending subsequence 】.

Why? ？ It's not hard to find that > Also have 【 One way transitivity 】

The third point ：
This question is not to ask 【 The length of the ascending subsequence 】, But for 【 Ascending subsequence 】. Then we only need an extra path Array , Record the position of the last smaller element of an element （ What is the previous element of the current element ）（ Or say , Of this element dp Where did the state transfer from ）.

Code

class Solution {
    
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
    
        vector<int> ans;
        int n = nums.size();
        vector<int> dp(n,1);
        // The path of the previous 
        vector<int> path(n,-1);
        // Sort 
        sort(nums.begin(),nums.end());
        // The endpoint pointer of the largest subset 
        int p = 0;
        // Find the value of the largest subset 
        int maxAns = 0;
        /* *  If a%b == 0 ,b%c == 0 , that  a%c == 0 （ One way transitivity ） *  The idea is similar to 【 Longest ascending subsequence 】 */
        for(int i=1;i<n;i++){
    
            for(int j=0;j<i;j++){
    
                if(nums[i] % nums[j] == 0){
    
                    if(dp[i] <= dp[j]){
    
                        dp[i] = dp[j]+1;
                        path[i] = j;
                    }
                }
                if(maxAns < dp[i]){
    
                    maxAns = dp[i];
                    p = i;
                }
            }
        }

        while(p != -1){
    
            ans.push_back(nums[p]);
            p = path[p];
        }
        return ans;
    }
};

Algorithm complexity

Time complexity ： O(n²). The sorting time is O(nlogn). Calculation dp The complexity of array elements is O(n²).
Spatial complexity ： O(n).dp The array needs O(n),path The array needs O(n).