# Java DP Solution With Explanation

• I think this problem somehow resembles "Russian Doll Envelope".
Logic: sort numbers from small to large.
Create a dp, where dp[i] contains longest divisible subset originating from num[i].
Iterate through, if num[r] is divisible by num[l], we consider extending the subset at dp[l], should the new subset is longer than existing one.
In the end, every dp[i] contains the longest subset originating from num[i]; simply pick the longest one to return.
Performance: time O(n^2); space: ~O(n^2).

``````public List<Integer> largestDivisibleSubset(int[] nums) {
// each entry dp[i] contains longest subset with head=num[i].
List<List<Integer>> dp = new ArrayList<>(nums.length);
for (int i = 0; i < nums.length; i++) {
}
Arrays.sort(nums);
// from largest to smallest
for (int r = nums.length-1; r >= 0; r--) {
for (int l = r-1; l >= 0; l--) {
if (nums[r] % nums[l] == 0 && dp.get(l).size() < dp.get(r).size() + 1) {
dp.set(l, list);
}
}
}
List<Integer> result = new ArrayList<>();
for (List<Integer> list : dp) {
if (list.size() > result.size())
result = list;
}
return result;
}``````

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