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


  • 34

    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){
                res.add(nums[i]);
                temp = nums[i];
                curDp--;
            }
        }
        return res;
    }

  • -4
    Y
    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


  • 12
    Y

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


  • 0
    H

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

    }


  • 2
    S

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


  • 1

    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!


  • 5
    A

    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)
                {
                    ans.add(nums[i]);
                    num = nums[i];
                    index = i;
                }
            }
            Collections.sort(ans);
            return ans;
        }
    }
    

  • 2
    F

    Thanks for your solution!
    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) {
                    res.add(0, nums[i]);
                    divisor = nums[i];
                    curDp--;
                }
            }
            return res;
        }
    }
    

  • 0
    S

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


  • 2
    A

    @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]


  • 2
    P

    @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.
    @markieff Could you please update your solution ?
    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){
                res.add(nums[i]);
                temp = nums[i];
                curDp--;
            }
        }
        return res;
    }
    

  • 0

    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<>());
    	    map.get (num).add (num);
            }
            
            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;
    }

  • 0
    M

    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?


  • 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]
    

  • 1
    C

    @cloud.runner said in Easy understood Java DP solution in 28ms with O(n^2) time:

    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);
                    }
                }
            }
    

  • 0
    T

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


  • 4
    C

    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){
                    res.add(nums[i]);
                    temp = nums[i];
                    maxIndex = i;
                }
            }
            Collections.sort(res);
            return res;
        }
    

  • 0
    W

    @conghuis said in Easy understood Java DP solution in 28ms with O(n^2) time:

    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];
       result.add(val);
       
       //往前寻找每一个值
       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];
               result.add(val);
               
           }
           
           firstIndex--;
           
           
           
       }
       
       return result;
    

    }


  • 0
    C

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

  • 0
    C

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


Log in to reply
 

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