###### tags: `Leetcode` `medium` `dynamic programming` `sort` `python` `c++`

# 368. Largest Divisible Subset

## [題目連結:] https://leetcode.com/problems/largest-divisible-subset/

## 題目:
Given a set of **distinct** positive integers ```nums```, return the largest subset ```answer``` such that every pair (```answer[i], answer[j]```) of elements in this subset satisfies:

* answer[i] % answer[j] == 0, or
* answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

**Example 1:**

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

**Example 2:**

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

## 解題想法:
* 此題要求找出數組中，最大的**可整除子集合**
* 內含的數字皆可滿足大的數字可以被小的數字整除
* DP:
* **需先將nums進行sort至由小到大排序(升序)**
* 排序好的nums以sortedNums代稱

		nums.sort() #sortedNums

* 定義dp[i]:
* 到sortedNums[i]為止，含有sortedNums[i]的最大可整除子集合

		dp=[[val] for val in nums]

* 雙迴圈判斷:
* **第一圈**: for i in range(1,len(nums))
* **目的**: 依序判斷sortedNums[0]~sortedNum[n-1]是否可以加入到sortedNum[n]
* **第二圈**: for j in range(i) 判斷
* if nums[i]%dp[j][-1]==0:
* 解釋: **dp[i]直接由整個dp[j]擴增，因為最後一個可以整除，則質因數皆可整除**
* if len(dp[i])<len(dp[j])+1:
* 解釋: 比先前的dp[j]短，才有擴增必要
* res = res if len(res)>len(dp[i]) else dp[i]

## Python:

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res=[]
        if len(nums) == 0 or len(nums)==1:
            return nums
        nums.sort() #升序
        #dp[i]表示 到sortedNums[i]為止 含有sortedNums[i]的最大可整除子集合
        dp=[[val] for val in nums]
        for i in range(1,len(nums)): #依序判斷sortedNums[0]~sortedNum[n-1]是否可以加入到sortedNum[n]
            for j in range(i):
                if nums[i]%dp[j][-1]==0 and len(dp[i])<len(dp[j])+1:
                    #dp[i]直接由整個dp[j]擴增，因為最後一個可以整除 質因數皆可整除
                    dp[i]=dp[j]+[nums[i]]
            res = res if len(res)>len(dp[i]) else dp[i]
            print(dp)
        return res

nums = [1,2,4,8]
result=Solution()
ans=result.largestDivisibleSubset(nums)
print('ans:',ans)

## C++:

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n=nums.size();
        if (n==0 || n==1)
            return nums;
        vector<int> res;
        vector<vector<int>> dp(n, vector<int>());
        sort(nums.begin(), nums.end());
        //init dp
        for (int i=0; i<n; i++){
            dp[i].push_back(nums[i]);
        }
        //dp
        for (int i=1; i<n; i++){
            for (int j=0; j<i; j++){
                int tmp=dp[j].size();
                if ((nums[i]%dp[j][tmp-1]==0) && (dp[i].size()<dp[j].size()+1)){
                    dp[i]=dp[j];
                    dp[i].push_back(nums[i]);
                }
            }
            res= (res.size()>dp[i].size())? res: dp[i];
        }
        return res;
    }
};