368. 最大整除子集

向右看齐 2022-10-09 12:15 117阅读 0赞

> 给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer\[i\], answer\[j\]) 都应当满足：  
> answer\[i\] % answer\[j\] == 0 ，或  
> answer\[j\] % answer\[i\] == 0  
> 如果存在多个有效解子集，返回其中任何一个均可。
> 
> 示例 1：
> 
> 输入：nums = \[1,2,3\]  
> 输出：\[1,2\]  
> 解释：\[1,3\] 也会被视为正确答案。  
> 示例 2：
> 
> 输入：nums = \[1,2,4,8\]  
> 输出：\[1,2,4,8\]
> 
>

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;
    
        }
    }