# Java DP Solution with Explanation

• 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 }));

}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.