Java实现 LeetCode 368 最大整除子集

368. 最大整除子集

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。

示例 1:

输入: [1,2,3]

输出: [1,2] (当然, [1,3] 也正确)

示例 2:

输入: [1,2,4,8]

输出: [1,2,4,8]

class Solution {

  public int max(int a,int b){

        return a>b?a:b;

    }

    public List<Integer> largestDivisibleSubset(int[] nums) {

        int n=nums.length;

        if(n==0)

            return new ArrayList();

        int[] last=new int[n];

        for(int i=0;i<n;i++)

            last[i]=-1;

        int[] dp=new int[n];

        int ans=0;

        Arrays.sort(nums);

        for(int i=0;i<n;i++)

            for(int j=0;j<i;j++){

                if(nums[i]%nums[j]==0&&dp[j]+1>dp[i]){

                    dp[i]=dp[j]+1;

                    if(dp[ans]<dp[i])

                        ans=i;

                    last[i]=j;

                }

            }

        List<Integer> ansList=new ArrayList();

        while(ans!=-1){

            ansList.add(nums[ans]);

            ans=last[ans];

        }

        return ansList;

    }

}

巴特西

Java实现 LeetCode 368 最大整除子集

368. 最大整除子集

最新文章

热门文章