# Classic DP solution similar to LIS, O(n^2)

• Use DP to track max Set and pre index.

``````public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
int[] count = new int[n];
int[] pre = new int[n];
Arrays.sort(nums);
int max = 0, index = -1;
for (int i = 0; i < n; i++) {
count[i] = 1;
pre[i] = -1;
for (int j = i - 1; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {
if (1 + count[j] > count[i]) {
count[i] = count[j] + 1;
pre[i] = j;
}
}
}
if (count[i] > max) {
max = count[i];
index = i;
}
}
List<Integer> res = new ArrayList<>();
while (index != -1) {
index = pre[index];
}
return res;
}
}``````

• well, it's not a dp solution....

• Very nice solution, code is clear and doesn't need more comments, very impressed!

• This post is deleted!

• what's the meaning of if (1 + count[j] > count[i]) ?

• This post is deleted!

• @yaqi13

To check if count[i] needs to be updated by count[j] +1.
A simple comparison between count[j] +1 and current value of count[i].

• Awesome solution.

• Great solution! Thank you!

• My take.

``````public List<Integer> largestDivisibleSubset(int[] nums) {
if (nums.length == 0) return new ArrayList<>();
Arrays.sort(nums);
Map <Integer, List<Integer>> map = new HashMap <>();
for (int num : nums) {
Integer copyKey = null;
for (Integer key : map.keySet())
if (num % key == 0)
if (copyKey == null || map.get (copyKey).size() < map.get (key).size()) copyKey = key;

map.put (num, copyKey != null ? new ArrayList<> (map.get (copyKey)) : new ArrayList<>());
}

List<Integer> max = null;
for (Map.Entry<Integer, List<Integer>> entry : map.entrySet())
if (max == null || max.size() < entry.getValue().size()) max = entry.getValue();
return max;
}
``````

• Same idea. Instead, using an array of Arraylist to store current valid subsets for every element in the original list.

``````public static List<Integer> largestDivisibleSubset(int[] nums) {
if (nums.length == 0) return new ArrayList<Integer>();
//sort the array first
Arrays.sort(nums);
ArrayList<Integer>[] dp = (ArrayList<Integer>[]) new ArrayList[nums.length];
int maxindex = 0;
int maxsize = -1;
int finalindex = 0;
int finalsize = -1;
for (int i = 0; i < nums.length; i++) {
dp[i] = new ArrayList<Integer>();
for (int j = i-1; j >= 0; j--) {
//if nums[i] can be divided by nums[j], it can also be divided by every element in dp[j].
//Find a previous nums[j] that has most element in
if (nums[i] % nums[j] == 0) {
if (dp[j].size() > maxsize) {
maxsize = dp[j].size();
maxindex = j;
}
}
}
//if maxsize not equal to -1, which means divisor for nums[i] is found,
//add the one with most element in.
if (dp[i].size() > finalsize) {
finalsize = dp[i].size();
finalindex = i;
}
maxindex = 0;
maxsize = -1;

}
return dp[finalindex];
}
``````

• @sodapeng Awesome!

• if (1 + count[j] > count[i])

This line is smart!

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