Java DP Solution With Explanation


  • -1
    A

    I think this problem somehow resembles "Russian Doll Envelope".
    Logic: sort numbers from small to large.
    Create a dp, where dp[i] contains longest divisible subset originating from num[i].
    Iterate through, if num[r] is divisible by num[l], we consider extending the subset at dp[l], should the new subset is longer than existing one.
    In the end, every dp[i] contains the longest subset originating from num[i]; simply pick the longest one to return.
    Performance: time O(n^2); space: ~O(n^2).

    public List<Integer> largestDivisibleSubset(int[] nums) {
        // each entry dp[i] contains longest subset with head=num[i].
        List<List<Integer>> dp = new ArrayList<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            List<Integer> list = new LinkedList<>();
            list.add(nums[i]);
            dp.add(list);
        }
        Arrays.sort(nums);
        // from largest to smallest
        for (int r = nums.length-1; r >= 0; r--) {
            for (int l = r-1; l >= 0; l--) {
                if (nums[r] % nums[l] == 0 && dp.get(l).size() < dp.get(r).size() + 1) {
                    List<Integer> list = new LinkedList<>(dp.get(r));
                    list.add(0, nums[l]);
                    dp.set(l, list);
                }
            }
        }
        List<Integer> result = new ArrayList<>();
        for (List<Integer> list : dp) {
            if (list.size() > result.size())
                result = list;
        }
        return result;
    }

Log in to reply
 

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