# 29-line clear java DP solution

• ``````public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int len = nums.length;
if (len == 0) {
return ret;
}
Arrays.sort(nums);
int[] f = new int[len];
int[] pre = new int[len];
int pos = 0;
for (int i = 0; i < len; i ++) {
f[i] = 1;
pre[i] = -1;
for (int j = 0; j < i; j ++) {
if (nums[i] % nums[j] == 0 && f[j] + 1 > f[i]) {
f[i] = f[j] + 1;
pre[i] = j;
}
}
pos = f[pos] < f[i] ? i : pos;
}
while (pos != -1) {
pos = pre[pos];
}
return ret;
}
}
``````

``````public List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
Arrays.sort(nums);
int[] count = new int[nums.length], parents = new int[nums.length];
int maxIdx = 0;
for (int i = 0, j; i < nums.length; maxIdx = count[i] > count[maxIdx] ? i : maxIdx, i++)
for (j = 0, count[i] = 1, parents[i] = -1; j < i; j++)
if (nums[i] % nums[j] == 0 && count[j] + 1 > count[i]) {
count[i] = count[j] + 1;
parents[i] = j;
}
for (; maxIdx != -1; maxIdx = parents[maxIdx])