368. 最大整除子集

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
  //排序
  Arrays.sort(nums);

  //记录当前点的来源
  int [] g=new int[nums.length+1];
  //记录每一点的最大值
  int [] dp=new int[nums.length+1];
  //i代表当前元素
  for(int i=0;i<nums.length;i++){
      int len=1,prev=i;//代表最小长度是1,有自身转移而来

      //j代表i之前的所有元素
      for(int j=0;j<i;j++){
          //如果能够整除
          if(nums[i]%nums[j]==0){
              //判断当前j最大值+1是否大于我们假设的最大值
              if(dp[j]+1>len){
              len=dp[j]+1;
              prev=j;
          }
          }
      }
      g[i]=prev;
      dp[i]=len;
  }

    //遍历所有dp[i] 来获取最大值是多少以及他的下标
    int max=-Integer.MAX_VALUE;
    int index=-Integer.MAX_VALUE;

    for(int i=0;i<nums.length;i++){
        if(dp[i]>max){
            max=dp[i];
            index=i;
        }
    }
        //得到最大值以及他的下标,进行从后往前插入到集合里面

        List<Integer> ans=new ArrayList();
        while(ans.size()<max){
            ans.add(nums[index]);
            index=g[index];
        }

        Collections.sort(ans,(o1,o2)-> o1-o2);
            return ans;

    }
}