Short O(n^2) Java solution with solution


  • 0
    M

    It's the same approach as the dp solution to longest increasing subsequence.
    Let dp[i] = the largest subset you can form if you take nums[i] as your last number.

    public int[] largestDivisibleSubset(int[] nums) {
        if(nums==null||nums.length<2) return nums;
        Arrays.sort(nums);
        int[] dp = new int[nums.length]; // the max length subset if you take nums[i];
        int[] prev = new int[nums.length]; // remembers which number it points to
    
        Arrays.fill(dp,1);
        Arrays.fill(prev,-1);
        
        int max = 1;
        int start = 0;
        for(int i=1; i<nums.length; i++){
            for(int j=0; j<i; j++){
                if(nums[i]%nums[j]==0&&dp[i]<dp[j]+1){ // they're multiples and we can create a larger subset
                    dp[i]=dp[j]+1;
                    prev[i]=j;
                    if(dp[i]>=max){
                        max = dp[i];
                        start = i;
                    }
                }
            }
        }
        int i = max-1;
        int[] res = new int[max];
        while(start!=-1){
            res[i--]=nums[start];
            start = prev[start];
        }
        return res;
    }

Log in to reply
 

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