30ms O(n^2) time and O(n) space dynamic programming solution


  • 0
    I
    public List<Integer> largestDivisibleSubset(int[] nums) {
            if(nums == null || nums.length < 1){
                return new ArrayList<>();
            }
            Arrays.sort(nums);
            int counts[] = new int[nums.length];
            int lastIndexes[] = new int[nums.length];
            counts[0] = 1;
            lastIndexes[0] = -1;
            for(int i = 1; i < nums.length; i++){
                int curr = nums[i];
                int count = 0;
                int lastIndex = -1;
                for(int j = i-1; j >= 0; j--){
                    if(curr % nums[j] == 0){
                        if(counts[j] > count){
                            count = counts[j];
                            lastIndex = j;
                        }
                    }
                }
                counts[i] = count + 1;
                lastIndexes[i] = lastIndex;
            }
            int end = -1;
            int max = 0;
            for(int i = 0; i < nums.length; i++){
                if(max <= counts[i]){
                    max = counts[i];
                    end = i;
                }
            }
            List<Integer> list = new ArrayList<>(max);
            while(end != -1){
                list.add(nums[end]);
                end = lastIndexes[end];
            }
            return list;
            
        }

Log in to reply
 

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