最大整除子集
给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (SS) 都要满足：S % S = 0 或 S % S = 0。
如果有多个目标子集，返回其中任何一个均可。
示例 1:
输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)
示例 2:
输入: [1,2,4,8]
输出: [1,2,4,8]
解题分析:
如果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即可。
import java.util.*;
class Solution {
public static List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> result=new ArrayList<Integer>();
List<Integer> numsList=new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
numsList.add(nums[i]);
}
if(nums.length==0) return result;
Collections.sort(numsList,Collections.reverseOrder());
int len=numsList.size();
int curMax=1;
int k=0;
int[] par=new int[len];
int[] dp=new int[len];
Arrays.fill(dp,1);
for(int i=0;i<len;i++){
par[i]=i;
}
for(int i=1;i<len;i++){
for(int j=0;j<i;j++){
if(numsList.get(j)%numsList.get(i)!=0){
continue;
}
if(dp[i]<dp[j]+1){
par[i]=j;
dp[i]=dp[j]+1;
}
if(dp[i]>curMax){
curMax=dp[i];
k=i;
}
}
}
while(par[k]!=k){
result.add(numsList.get(k));
k=par[k];
}
result.add(numsList.get(k));
return result;
}
}