Java dp solution, O(n^2)


  • 0
    M
        public List<Integer> largestDivisibleSubset(int[] nums) {
            if(nums==null || nums.length==0) return new LinkedList<>();
            Arrays.sort(nums);
            int[] dp = new int[nums.length];
            // Arrays.fill(dp, 1);
            int maxIndex = 0;
            for(int i=0; i<nums.length; i++){
                int curMax = 0;
                for(int j=i-1; j>=0; j--){
                    if(nums[i]%nums[j]==0){
                        curMax = Math.max(curMax, dp[j]);
                        if(curMax == dp[maxIndex]) break;
                    }
                }
                dp[i] = curMax+1;
                if(dp[i]>dp[maxIndex])
                    maxIndex = i;
            }
            LinkedList<Integer> list = new LinkedList<>();
            list.addFirst(nums[maxIndex]);
            int curIndex = maxIndex;
            for(int i=maxIndex-1; i>=0; i--){
                if(dp[i]==dp[curIndex]-1 && nums[curIndex]%nums[i]==0){
                    list.addFirst(nums[i]);
                    curIndex = i;
                    if(dp[i]==1) break;
                }
            }
            return list;
        }
    

Log in to reply
 

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