# Easy understood Java DP solution in 28ms with O(n^2) time

• The basic idea is like:

``````1. Sort
2. Find the length of longest subset
3. Record the largest element of it.
4. Do a loop from the largest element to nums[0], add every element belongs to the longest subset.
``````

The old version cant pass the test case [1,2,4,8,9,72] and [4,8,10,240], thanks for that @Yanning and @svc
Here comes the revised version:

``````public static List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if (nums == null || nums.length == 0) return res;
Arrays.sort(nums);
int[] dp = new int[nums.length];
dp[0] = 1;

//for each element in nums, find the length of largest subset it has.
for (int i = 1; i < nums.length; i++){
for (int j = i-1; j >= 0; j--){
if (nums[i] % nums[j] == 0){
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
}

//pick the index of the largest element in dp.
int maxIndex = 0;
for (int i = 1; i < nums.length; i++){
maxIndex = dp[i] > dp[maxIndex] ?  i :  maxIndex;
}

//from nums[maxIndex] to 0, add every element belongs to the largest subset.
int temp = nums[maxIndex];
int curDp = dp[maxIndex];
for (int i = maxIndex; i >= 0; i--){
if (temp % nums[i] == 0 && dp[i] == curDp){
temp = nums[i];
curDp--;
}
}
return res;
}``````

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

the break here is the essential point

• I think you should not break immediately. Check the test case: [4,8,10,240]

• here is c#, easier to understand and keep tracks of previous elements -

public class Solution {
public IList<int> LargestDivisibleSubset(int[] nums) {
var numList = new List<int>(nums);
if(numList.Count == 0)
{
return numList;
}

``````    numList.Sort();

var dpCount = new int[nums.Length];
var dpPrev = new int[nums.Length];

for(int i= 0; i< nums.Length; i++)
{
dpCount[i] = 1;
dpPrev[i] = -1;
}

for(int i = 1; i< numList.Count; i++)
{
for(int j = i-1; j>=0; j--)
{
if(numList[i]% numList[j] == 0)
{
if(dpCount[j] + 1 > dpCount[i])
{
dpCount[i] = dpCount[j] + 1;
dpPrev[i] = j;
}
}
}
}

var max = dpCount[0];
var index = 0;

for(int i = 1; i< numList.Count; i++)
{
if(dpCount[i] > max)
{
max = dpCount[i];
index = i;
}
}

var result = new List<int>();

while (index != -1)
{
result.Insert(0, numList[index]);
index = dpPrev[index];
}

return result;

}
``````

}

• Caution to other readers. This code does not work for [1,2,4,8,9,72]. Found by @wad here.

• Sorry guys, although my code pass all the test cases given by Leetcode, there still are some test case it cant pass. Thanks for pointing out @Yanning. Appreciate that!

• I change your answer slightly and now it works on all test cases including [1,2,4,8,9,72]

``````public class Solution {
//DP
public List<Integer> largestDivisibleSubset(int[] nums) {
if (nums.length == 0)
return new ArrayList<>();
Arrays.sort(nums);
int n = nums.length;
int[] dp = new int[n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (nums[i] % nums[j] == 0)
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
int max = 0;
int index = 0;
for (int i = 0; i < n; i++)
{
if (dp[i] > max)
{
index = i;
max = dp[i];
}
}
List<Integer> ans = new ArrayList<>();
int num = nums[index];
for (int i = index; i >= 0; i--)
{
if (num % nums[i] == 0 && dp[index] - dp[i] <= 1)
{
num = nums[i];
index = i;
}
}
Collections.sort(ans);
return ans;
}
}
``````

Actually, we can get the "last index" within the first loop :)

``````public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return res;
}

Arrays.sort(nums);
int[] dp = new int[nums.length];
dp[0] = 1;
int lastIndex = 0;
int maxLength = 1;
// find the length of divisible sequence for every position
for (int i = 1; i < nums.length; i++) {
for (int j = i-1; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
// get the lastIndex
if (maxLength < dp[i]) {
maxLength = dp[i];
lastIndex = i;
}
}
// then add every divisible number before last index into the list
int divisor = nums[lastIndex];
int curDp = dp[lastIndex];
for (int i = lastIndex; i >= 0; i--) {
if (divisor % nums[i] == 0 && dp[i] == curDp) {
divisor = nums[i];
curDp--;
}
}
return res;
}
}
``````

• Hi,
this code doesn't work for [2,4,6,9,19,81,729]

• @markieff Hey, it does not pass the test case `[3,4,6,8,12,16,32]` . The expected answer is `[4,8,16,32]`. However, the answer your program shows is [12,6,3]

• @aritra90tnp You're right. In this test case `[3,4,6,8,12,16,32]` the value of `dp[1] = 0` instead it should be 1. So, we should initialize our `dp[ ]` array with 1 to get the right answer.
I changed just one 1 line in the following code to get the right answer. Although there might be a better way I suppose.

`````` public static List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if (nums == null || nums.length == 0) return res;
Arrays.sort(nums);
int[] dp = new int[nums.length];
dp[0] = 1;

//for each element in nums, find the length of largest subset it has.
for (int i = 1; i < nums.length; i++){
for (int j = i-1; j >= 0; j--){
if (nums[i] % nums[j] == 0){
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
dp[i] = dp[i] > 0 ? dp[i] : 1; // Just added this line.
}

//pick the index of the largest element in dp.
int maxIndex = 0;
for (int i = 1; i < nums.length; i++){
maxIndex = dp[i] > dp[maxIndex] ?  i :  maxIndex;
}
//from nums[maxIndex] to 0, add every element belongs to the largest subset.
int temp = nums[maxIndex];
int curDp = dp[maxIndex];
for (int i = maxIndex; i >= 0; i--){
if (temp % nums[i] == 0 && dp[i] == curDp){
temp = nums[i];
curDp--;
}
}
return res;
}
``````

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

• Great solution!
I have a question. The array int[] dp is initialized with value 0 for each element. However, it should be 1, since it can be divided by itself right?
Thus to be concise, the inner loop:

``````for (int j = i-1; j >= 0; j--){
if (nums[i] % nums[j] == 0){
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
``````

Shouldn't j start from i instead of i-1?

• hi @markieff I think the `dp[0] = 1;` is unnecessary, or it can NOT pass this test case:

``````Input:
[2,3,8,9,27]
Output:
[8,2]
Expected:
[3,9,27]
``````

• 2,3,8,9,27

dp[0] should be initialized to 1. In this case, you might need to do following change

``````        for (int i = 0; i < nums.length; i++) {
for (int j = i; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
``````

• Neat solution but IMHO `dp[0]` should be initialized as `0`

• I initialize all dp array elements as 1, and it passed all test cases.

``````    public List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if (nums == null || nums.length == 0)
return res;
Arrays.sort(nums);
int[] dp = new int[nums.length];
for(int i = 0; i < dp.length; i++){
dp[i] +=1;
}

for(int i = 0; i < nums.length; i++)
for(int j = 0; j <i ; j++){
if(nums[i] % nums[j] == 0)
dp[i] = Math.max(dp[i], dp[j] +1);
}

int maxIndex = 0;
for (int i = 1; i < nums.length; i++)
maxIndex = dp[i] > dp[maxIndex]? i: maxIndex;

int temp = nums[maxIndex];
int curDp = dp[maxIndex];
for(int i = maxIndex; i>=0; i--){
if(temp % nums[i] == 0 && dp[maxIndex] - dp[i] <=1){
temp = nums[i];
maxIndex = i;
}
}
Collections.sort(res);
return res;
}
``````

• I initialize all dp array elements as 1, and it passed all test cases.

this is my solution:
public static List<Integer> largestDivisibleSubset(int[] nums) {

``````   List<Integer> result=new ArrayList<Integer>();
if(nums==null||nums.length==0)
return result;

Arrays.sort(nums);

//dp[i]表示从0-i且包含i的最长子串长度
int[] dp=new int[nums.length];
dp[0]=1;
for(int i=1;i<nums.length;i++){

dp[i]=1;
for(int j=i-1;j>=0;j--){

if(nums[i]%nums[j]==0){
dp[i]=Math.max(dp[i],dp[j]+1);
}

}

}

//找出最大值的索引
int maxIndex=0;
for(int i=1;i<dp.length;i++){

if(dp[i]>dp[maxIndex])
maxIndex=i;

}

int val=nums[maxIndex];

//往前寻找每一个值
int secondIndex=maxIndex;
int firstIndex=maxIndex-1;
while(firstIndex>=0){

if(val%nums[firstIndex]==0&&dp[secondIndex]-dp[firstIndex]==1){
secondIndex=firstIndex;
val=nums[firstIndex];

}

firstIndex--;

}

return result;
``````

}

• You can actually locate the index of the biggest num in the longest group in the O(n ^2) for loop, no need for a separate for loop to find the index.

``````// find the len of longest group and the index of biggest num in the longest group
for (int i = 0; i < nums.length; i ++) {
for (int j = i + 1; j < nums.length; j ++) {
if (nums[j] % nums[i] == 0)
dp[j] = dp[i] + 1;
if (dp[j] > maxLen) {
maxLen = dp[j];
maxNumPos = j;
}
}
}
``````

• Miss initialization for dp[i]=1 i>0;

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