题目
题目来源：Link
分析
（1）数组排序，保证后面数的因子都在前面出现
（2）当前 nums[i] 与 0~i-1 间的 nums[k] 比较，取满足条件的 nums[k] 且 他代表的子集最大，将 nums[i] 加入。 因为要满足取余数为0， 则后面的都是前面的倍数，只要比较子集的尾巴，满足 nums[i] % nums[k] == 0，就不用再比较更前面的 nums[k]
（3）辅助变量 count[i] 记录当前 nums[i] 作为子集尾巴的最大子集数；pre[i] 记录 nums[i] 作为子集尾巴的前一个子集元素的 index
（4）找到最大的 count[i]，根据 pre数组反向遍历，得到子集
代码
package com.graph;
import java.util.*;
public class Solution{
List<Integer> res = new ArrayList<Integer>();
public List<Integer> solve(int[] nums){
if(nums==null || nums.length==0) return res;
Arrays.sort(nums);//这一步一定要，能保证因子都在前面出现了
int n = nums.length;
int[] count = new int[n];
int[] pre = new int[n];
Arrays.fill(count, 1);
Arrays.fill(pre, -1);
for(int i=1; i<n; i++){
int j=i-1;
int max=0;
int maxIndex=-1;
for(;j>=0; j--){
if(nums[i]%nums[j]==0 || nums[j]%nums[i]==0){
if(max<count[j]){
max = count[j];
maxIndex = j;
}
}
}
count[i]=max+1;
pre[i] = maxIndex;
}
int max = 0;
int maxIndex = -1;
for(int i=0; i<n; i++){
if(max<count[i]){
max = count[i];
maxIndex = i;
}
}
int preIndex = maxIndex;
while(preIndex!=-1){
res.add(nums[preIndex]);
preIndex = pre[preIndex];
}
return res;
}
public static void main(String[] args) {
Solution s = new Solution();
s.solve(new int[] {1,2,4,8,7,9,6,3});
}
}
