Java dp O(n^2) time O(n) space with comments


  • 0

    utilize the transitivity of divisibility, kind of like " Longest Increasing Subsequence" problem
    However this one requires you to return the actual subset rather than cardinality of the set,
    so you need to do some bookkeeping by using another array.

    public class Solution {
        public int[] largestDivisibleSubset(int[] nums) {
            if (nums == null || nums.length < 2) {
                return nums;
            }
            Arrays.sort(nums);
            int n = nums.length;
            int[] counts = new int[n];// cardinality of  subset end with nums[i]
            int[] previous = new int[n]; // biggest number (smaller than itself) which is divisible by nums[i]
            counts[0] = 1;
            previous[0] = -1;
            int max = 0;
            int maxIndex = -1;
            for (int i = 1; i < n; i++) {
                max = 0;
                maxIndex = -1;
                for (int j = 0; j < i; j++) {
                    if (nums[i] % nums[j] == 0 && counts[j] > max) {
                        max = counts[j];
                        maxIndex = j;
                    } 
                }
                counts[i] = max + 1;
                previous[i] = maxIndex;
            }
            max = maxIndex = 0;
            for (int i = 0; i < n; i++) {
                if (counts[i] > max) {
                    max = counts[i];
                    maxIndex = i;
                }
            }
            
            int[] subset = new int[max];
            int index = 0;
            //backtrack to get subset
            do {
                subset[index++] = nums[maxIndex];
                maxIndex = previous[maxIndex];
            } while (maxIndex != -1);
            
            return subset;
        }
    }

Log in to reply
 

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