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


  • 69
    J

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

  • -15
    T

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


  • 0

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


  • 0
    U
    This post is deleted!

  • 1

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


  • 0
    M
    This post is deleted!

  • 0

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


  • 0
    T

    Awesome solution.


  • 0

    Great solution! Thank you!


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

  • 1
    S

    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 (maxsize != -1) dp[i].addAll(dp[maxindex]);
    		//add nums[i] itself to dp
    		dp[i].add(nums[i]);
    		if (dp[i].size() > finalsize) {
    			finalsize = dp[i].size();
    			finalindex = i;
    		}
    		maxindex = 0;
    		maxsize = -1;
    
    	}
    	return dp[finalindex];
    }
    

  • 0
    N

    @sodapeng Awesome!


Log in to reply
 

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