题目链接： 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; } }
