Leetcode 368. Largest Divisible Subset

    xiaoxiao2021-03-25  9

    题目链接: Leetcode 368. Largest Divisible Subset  

    与求最大全联通子集同构?

    动态规划问题。

    import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Solution { public List<Integer> largestDivisibleSubset(int[] nums) { int n = nums.length; int[] pre = new int[n]; int[] count = new int[n]; int max = 0, index = -1; Arrays.sort(nums); for(int i=0;i<n;i++){ //init for count and pre count[i] = 1; pre[i] = -1; for(int j=i-1;j>=0;j--){ if(nums[i]%nums[j]==0){ if(count[j]+1>count[i]){ count[i] = count[j]+1; pre[i] = j; } } } if(count[i]>max){ max = count[i]; index = i; } } List<Integer> subset = new ArrayList<Integer>(); while(index!=-1){ subset.add(nums[index]); index = pre[index]; } return subset; } }

    转载请注明原文地址: https://ju.6miu.com/read-200243.html

    最新回复(0)