Concise Java Solution using DP + HashMap


  • 0
    X
    public class Solution {
        public List<Integer> largestDivisibleSubset(int[] nums) {
            if(nums.length == 0) return (new ArrayList<Integer>());
            Arrays.sort(nums);
            Map<Integer, Integer> map = new HashMap<>();
            int[] dp = new int[nums.length], dp[0] = 1;
            int maxV = 1, index = 0;
            for (int i = 1; i < nums.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] % nums[j] == 0) {
                        if (dp[j] + 1 > dp[i]) {
                            dp[i] = dp[j] + 1;
                            map.put(nums[i], nums[j]);  // backward index
                        }
                        if (dp[i] > maxV) {
                            maxV = dp[i];
                            index = i;
                        }
                    } 
                }
            }
            List<Integer> ret = new ArrayList<Integer>();
            int key = nums[index];
            ret.add(key);
            while (map.containsKey(key)) {
                ret.add(map.get(key));
                key = map.get(key);
            }
            return ret;        
        }
    }

Log in to reply
 

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