[leetcode] 368. Largest Divisible Subset

Description

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:

Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)      

Example 2:

Input: [1,2,4,8]
Output: [1,2,4,8]      

分析

• 最好的方法還是動态規劃，這道題dp[i]表示數字nums[i]位置最大可整除的子集合的長度，還需要一個一維數組parent，來儲存上一個能整除的數字的位置，兩個整型變量mx和mx_idx分别表示最大子集合的長度和起始數字的位置；
• 我們可以從後往前周遊數組，對于某個數字再周遊到末尾，在這個過程中，如果nums[j]能整除nums[i], 且dp[i] < dp[j] + 1的話，更新dp[i]和parent[i]，如果dp[i]大于mx了，還要更新mx和mx_idx，最後循環結束後，我們來填res數字，根據parent數組來找到每一個數字。

代碼

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        vector<int> result;
        sort(nums.begin(),nums.end());
        vector<int> dp(nums.size(),0);
        vector<int> parent(nums.size(),0);
        int mx=0;
        int mx_idx=0;
        for(int i=nums.size()-1;i>=0;i--){
            for(int j=i;j<nums.size();j++){
                if(nums[j]%nums[i]==0&&dp[i]<dp[j]+1){
                    dp[i]=dp[j]+1;
                    parent[i]=j;
                    if(mx<dp[i]){
                        mx=dp[i];
                        mx_idx=i;
                    }
                }
            }
        }
        for(int i=0;i<mx;i++){
            result.push_back(nums[mx_idx]);
            mx_idx=parent[mx_idx];
        }
        return result;
    }
 
};      

參考文獻