题目描述：
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，则a=mb，所以如果把数组排序后如果a%b==0，且b%c==0则a%c==0。这就为用动态规划实现提供了可能性。设置一个数组result，result[i]表示i出包含的满足条件的子集个数。则如果nums[i]%nums[j]==0，则result[i]=result[j]+1;同时由于函数要返回的是一个List，所以我们要保存最长集合的路径。这个功能可以通过设置一个pre数组保存能被nums[i]整除的上一个数的索引。并在保存max值的同时保存max所在的位置maxIndex即可。
public class Solution {
public static List<Integer> largestDivisibleSubset(int[] nums) {
if(nums.length==0){
return new ArrayList<Integer>();
}
if(nums.length==1){
List<Integer> array = new ArrayList<Integer>();
array.add(nums[0]);
return array;
}
Arrays.sort(nums);
int len = nums.length;
int[] result=new int[len];
int[] pre=new int[len];
result[0]=nums[0];
pre[0]=-1;
int max=1;
int maxIndex=0;
for(int i=1;i<nums.length;i++){
result[i]=1;
pre[i]=-1;
for(int j=0;j<i;j++){
if(nums[i]%nums[j]==0){
result[i]=result[j]+1;
pre[i]=j;
if(result[i]>max){
max=result[i];
maxIndex=i;
}
}
}
}
List<Integer> array = new LinkedList<Integer>();
int index = maxIndex;
while(index!=-1){
array.add(0,nums[index]);
index=pre[index];
}
return array;
}
}