# Java dp solution: two arrays to store length and sequence

• Use two arrays for this dp solution
Array dp will store the length of the largest subset
Array prev will store the index of the element along the sequence
dp need to fill 1 because the smallest subset will contain itself and have length of 1

`````` public List<Integer> largestDivisibleSubset(int[] nums) {

List<Integer> ret = new ArrayList<Integer>();

if (nums == null || nums.length == 0)
return ret;

Arrays.sort(nums);

int[] dp = new int[nums.length];
int[] prev = new int[nums.length];
Arrays.fill(dp, 1);
prev[0] = 0;

for (int i = 1; i < nums.length; i++) {
for (int j = i-1; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {

if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}

}
}
}

// find the max of dp
int maxIndex = 0;
for (int i = 0; i < dp.length; i++) {
if (dp[i] > dp[maxIndex]) {
maxIndex = i;
}
}

int len = dp[maxIndex];

while (true) {
maxIndex = prev[maxIndex];

if (--len <= 0)
break;
}

return ret;

}
``````

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