Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

nums: [1,2,3]Result: [1,2] (of course, [1,3] will also be ok)

 

Example 2:

nums: [1,2,4,8]Result: [1,2,4,8] 分析：

思路: 将数组排序，然后用dp[i]表示从0到i最大的集合。为了得到dp[i]的值, 我们从i - 1 到 0 看是否 nums[i] % nums[j] ==0,  如果是，dp[i] = max(dp[i], dp[j]+1), 因为数组按照降序排序, 所以nums[j] < nums[i],并且之前能够被nums[j]整除的数, 也必然能够被 nums[i]整除。

1 public class Solution { 2     public List
     
       largestDivisibleSubset(int[] nums) { 3         if (nums == null || nums.length == 0) return new ArrayList
      
       (); 4  5         int n = nums.length; 6         Arrays.sort(nums); 7         int[] dp = new int[n]; 8         Arrays.fill(dp, 1); 9         int[] parent = new int[n];10         Arrays.fill(parent, -1);//当parent数组中某数为-1时，表示这个数自己是一个集合11         int max = 1, max_index = 0; 12         for (int i = 1; i < n; i++) {   //calculate dp[i]13             for (int j = i - 1; j >= 0; j--) {  //i > j14                 if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {    //positive distinct numbers in num15                     dp[i] = dp[j] + 1;16                     parent[i] = j;17                     if (dp[i] > max) {18                         max = dp[i];19                         max_index = i;20                     }21                 }22             }23         }24         return genResult(nums, parent, max_index);25     }26     27     public List
       
         genResult(int[] nums, int[] parent, int max_index) {28         List
        
          result = new ArrayList<>();29         int iter = max_index;30         while (iter != -1) {31             result.add(nums[iter]);32             iter = parent[iter];33         }34         return result;35     }36 }