public class LargestDivisibleSubset {

/*

* Solution: Use DP thought. 1.Set count[i] to record the length of list

* while using nums[i] as the tail of the list and parent[i] to record the

* front element of nums[i]'s index 2.When we get a new element, we set the

* count[curr] the maximum of (count[j] + 1) while (nums[curr] % nums[j] ==

* 0) and set parent[curr] j 3.For not scanning the count[] again, we also

* set maxIndex and max to record them. 4.Finally we just recover the list

* by maxIndex and nums[]

*/

```
public List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> res = new LinkedList<>();
if (nums.length == 0)
return res;
int[] count = new int[nums.length];
int[] parent = new int[nums.length];
Arrays.sort(nums);
count[0] = 1;
parent[0] = -1;
int maxIndex = 0;
int max = 0;
for (int i = 1; i < nums.length; i++) {
int maxCount = 1;
int currParent = -1;
for (int j = i - 1; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {
if (maxCount < count[j] + 1) {
maxCount = count[j] + 1;
currParent = j;
}
}
}
count[i] = maxCount;
parent[i] = currParent;
if (count[i] > max) {
max = count[i];
maxIndex = i;
}
}
for (int i = maxIndex; i != -1; i = parent[i]) {
res.add(0, nums[i]);
}
return res;
}
public static void main(String[] args) {
System.out.println(new LargestDivisibleSubset().largestDivisibleSubset(new int[] { 1, 2, 4, 8 }));
}
```

}