LeetCode-Largest Divisble Subset

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 @Stomach_ache 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:

 public class Solution {
     public List<Integer> largestDivisibleSubset(int[] nums) {
         List<Integer> resList = new LinkedList<Integer>();
         if (nums.length == 0) return resList;         Arrays.sort(nums);
         int[] size = new int[nums.length];
         int[] pre = new int[nums.length];         int maxSize = 0;
         int maxInd = -1;         for (int i=0;i<nums.length;i++){
             int localMax = 0;
             int localInd = -1;
             for (int j=0;j<i;j++)
                 if (nums[i] % nums[j] == 0 && localMax < size[j]+1){
                     localMax = size[j]+1;
                     localInd = j;
                 }
             if (localInd == -1){
                 localMax = 1;
                 localInd = -1;
             }
             size[i] = localMax;
             pre[i] = localInd;             if (maxSize < localMax){
                 maxSize = localMax;
                 maxInd = i;
             }
         }         resList.add(nums[maxInd]);
         int preInd = pre[maxInd];
         while (preInd != -1){
             maxInd = preInd;
             preInd = pre[maxInd];
             resList.add(nums[maxInd]);
         }
         Collections.reverse(resList);         return resList;
     }
 }