Given a set of distinct positive integers, find the largest subset such that every pair (S_i, S_j) of elements in this subset satisfies: S_i % S_j = 0 or S_j % S_i = 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]

Credits:

Special thanks to for adding this problem and creating all test cases.

Analysis:

Sort the array, then for nums[i], if nums[i] % nums[j] == 0, then nums[i] is in the largest divisible set of nums[j]. We just need to find out the largest subset of nums[i].

Solution:

1 public class Solution { 2     public List
     
       largestDivisibleSubset(int[] nums) { 3         List
      
        resList = new LinkedList
       
        ();         4         if (nums.length == 0) return resList; 5  6         Arrays.sort(nums); 7         int[] size = new int[nums.length]; 8         int[] pre = new int[nums.length]; 9 10         int maxSize = 0;11         int maxInd = -1;12 13         for (int i=0;i