http://lintcode.com/en/problem/largest-divisible-subset/
https://leetcode.com/problems/largest-divisible-subset/discuss/
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.
这个题难点：
如何判断一个数 a 能被集合 set 里面所有的数整除，这个整除只要一个方向a % b 或者 b % a满足就可以了。
办法：
这个和最长递增子序列是一样的，接龙性dp问题
假定集合set = {max, ..., min}， 这个集合是满足条件的
如果数a 比集合里的最大数大，那么就看a % max == 0， 如果满足，就可以加入集合
如果数a 比集合里的最小数小， 那么就看max % a == 0 或者 min % a == 0
如果数a 处于中间， 那么就看 max % a == 0
所以我们从最大数a 开始，遍历所有之前的集合，看是否能把a 放入集合，如果能就看看加入这个a后，新集合的大小就可以更新了。
而对于之前的集合同样方法，遍历所有它之前的集合。
最终就是一个自顶向下的dfs。
所以我们从最小数开始建立集合，就是dp了。
# https://leetcode.com/problems/largest-divisible-subset/discuss/
class Solution:
# @param {int[]} nums a set of distinct positive integers
# @return {int[]} the largest subset
def largestDivisibleSubset(self, nums):
# Write your code her
n = len(nums)
nums.sort()
# dp[n] = the length of the largest divisible subset whose largest number is nums[n]
dp = [1] * n
father = [-1] * n
maxLen = 1
index = 0
for i in xrange(n):
for j in range(i):
if nums[i] % nums[j] == 0:
if dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
father[i] = j
if dp[i] > maxLen:
maxLen = dp[i]
index = i
result = []
while index >= 0:
result.append(nums[index])
index = father[index]
return result
