题目链接：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.
题目意思也很简单，给出一个不含重复数字的数组，找到最长的一个子数组，子数组里的元素必须两两整除。
这里有个很简单的数学性质，就是整除的传递性，如果a%b==0 且 b%c == 0，那么a%c == 0，说白了如果c是b的因子，b又是a的因子，那么c肯定是a的因子。这样我们就可以在数组中找出很多整除链（a->b->c->d，其中b是a的因子，c是b的因子，d是c的因子），这样的链条就满足两两整除的条件，题目就变成了求最长的链条。
先上代码，然后我再解释下我的代码。
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Solution { public List<Integer> largestDivisibleSubset(int[] nums) { List<Integer> ret = new ArrayList<Integer>(); if (nums.length < 2) { if (nums.length == 0) return ret; ret.add(nums[0]); return ret; } Arrays.sort(nums); int[] prefactors = new int[nums.length]; int[] factorcount = new int[nums.length]; int maxlength = 0; int maxnum = 0; for (int i = nums.length-1; i >= 0; i--) { for (int j = i; j < nums.length; j++) { if (nums[j]%nums[i] == 0 && factorcount[i] < factorcount[j]+1) { factorcount[i] = factorcount[j]+1; prefactors[i] = j; if (factorcount[i] > maxlength) { maxlength = factorcount[i]; maxnum = i; } } } } for (int i = 0; i < maxlength; i++) { ret.add(nums[maxnum]); maxnum = prefactors[maxnum]; } return ret; } }
首先我先对nums排序，这里我用了两个数组prefactors[]和factorcount[]，prefactors[i]里其实保存的是以nums[i]未结尾的整除链前面一个数的下标，factorcount[i]存的是以nums[i]结尾的整除链长度。这里我们就可以用动态规划的方式求出factorcount[i]的值了，取最大的一个，然后再根据prefactors[i]推算出整除链中所有的元素。
这里开两个脑洞，发散下思维。
脑洞1：
其实所有整除链可以合并为一个多叉整除树，这里得增加一个额外的根节点，使得根节点可以被nums中任何一个数整除。这个整除树有个很重要的性质——除根节点以为任意节点可以整除其父节点。 这道题就会演变成求整除树中最深的路径。 对于树的问题，我们往往能用递归的方式解决，代码也会变得比较好理解。
脑洞2：
看下代码，是不是很像01背包，其实我觉得这到题可以认为是带限制条件的01背包，限制条件可以简化为放入背包的数必须能整除背包中最小的一个数，背包为无穷大，每个数的价值为1。
