Java Solution in 32ms O(N^2) time, O(N) space


  • 14
    F
    public class Solution {
        public int[] largestDivisibleSubset(int[] nums) {
            if(nums.length < 2)
                return nums;
            else{
                Arrays.sort(nums);
                int[] parent = new int[nums.length];
                int[] count = new int[nums.length];
                int max = 0, maxind = -1;
                for(int i = nums.length - 1; i >= 0; i--){
                    for(int j = i; j < nums.length; j++){
                        if(nums[j] % nums[i] == 0 && count[i] < 1 + count[j] ){
                            count[i] = 1 + count[j];
                            parent[i] = j;
                            if(count[i] > max){
                                max = count[i];
                                maxind = i;
                            }
                        }
                    }
                }
                int[] res = new int[max];
                for(int i = 0; i < max; i++){
                    res[i] = nums[maxind];
                    maxind = parent[maxind];
                }
                return res;
            }
        }
    }

  • 0
    D

    @fatalme anyone think this is better than DP solution?


  • 0

    @dimi This is DP solution.


  • 0
    X

    nice usage of parent array


Log in to reply
 

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