# 368. Largest Divisible Subset 最大整除子集

## # 题目描述：

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]
``````

## # 解题方法

1. 寻找最长的满足题目的数组
2. 输出整个结果

``````注意这个case：
[1,2,4,8,9,72]

``````

``````class Solution:
def largestDivisibleSubset(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums: return []
N = len(nums)
nums.sort()
dp = [0] * N #LDS
parent = [0] * N
mx = 0
mx_index = -1
for i in range(N):
for j in range(i - 1, -1 , -1):
if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
parent[i] = j
if dp[i] > mx:
mx = dp[i]
mx_index = i
res = list()
for k in range(mx + 1):
res.append(nums[mx_index])
mx_index = parent[mx_index]
return res[::-1]
``````

https://segmentfault.com/a/1190000005922634 http://www.cnblogs.com/grandyang/p/5625209.html

## # 日期

2018 年 10 月 12 日 —— 又要到周末了！