368. Largest Divisible Subset.md

368. Largest Divisible Subset

思路

给定一个全为正数的集合（集合内的元素是互不相等且无序的），要求返回一个子集，使得子集中任意两个元素都能整除。

由于考虑是否满足整除的时候需要先考虑两数的大小，比较麻烦，所以我们可以先对nums数组进行排序。 排序还有一个好处就是如果集合{x0, x2}（x0 < x2）是满足要求的集合，那么如果此时新来一个更大的元素x3，我们只需判断x3能否被x2整除，如果能就那x3加进去； 而不用再判断x3是否能被x0整除，因为x2能被x0整除，所以如果x3能被x2整除那么它肯定也能被x0整除。

可见上述过程可以用一个动归来建模，由于最后返回的是集合而不是集合大小，所以我们需要两个动归数组：

• len[i]表示以nums[i]结尾（即最大元素是nums[i]）的满足题意的最大集合的大小；
• pre[i]表示上述最大集合中排在nums[i]前面的元素（即次大的元素）是nums[pre[i]]。

pre数组是为了最后能够从结果集合的最后一个元素不断追踪回去得到整个集合。

转移方程类似求最长递增子序列的动归过程：

// 注意更新时要同时更新pre[i]
for all j < i and (nums[i] % nums[j] == 0):
    len[i] = max(len[i], len[j] + 1) 

题目返回的是全局的结果，所以我们需要两个全局变量分别表示len[:]的最大值及对应的下标。

排序复杂度是O(nlogn)，但是动归的时候是个两层循环，时间复杂度为O(n^2)，空间复杂度为O(n)。 由于这里求的是集合而不是集合大小，所以没法用滚动数组将空间优化到O(1)，至少开辟一个pre数组。

C++

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if(nums.size() <= 1) return nums;
        
        sort(nums.begin(), nums.end());
        
        vector<int>len(nums.size(), 1);
        vector<int>pre(nums.size(), -1);
        
        int max_len = 0, max_i = -1;
        for(int i = 1; i < nums.size(); i++){
            for(int j = i - 1; j >= 0; j--){
                if(nums[i] % nums[j] == 0 && len[i] < len[j] + 1){
                    len[i] = len[j] + 1;
                    pre[i] = j;
                }
            }
            
            if(max_len < len[i]){
                max_len = len[i];
                max_i = i;
            } 
        }
        
        vector<int>res;
        while(max_i >= 0){
            res.push_back(nums[max_i]);
            max_i = pre[max_i];
        }
        return res;
    }
};