Leetcode 368.最大整除子集

最大整除子集

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (S_i，S_j) 都要满足：S_i % S_j = 0 或 S_j % S_i = 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;
    }
}