Share my DP Java Solution


  • 0

    After browsing the disscusions under the tag Dynamic Programming, it is really interesting that with DP, many different people wrote the same code, and it seems that DP works like a charm in many times.

    public class Solution368LargestDivisibleSubset {
    
        public List<Integer> largestDivisibleSubset(int[] nums) {
            if (nums == null || nums.length == 0)
                return new ArrayList<>();
            if (nums.length == 1)
                return Arrays.asList(nums[0]);
            Arrays.sort(nums);
            int[] subsetSize = new int[nums.length];
            int[] prevIndex = new int[nums.length];
            Arrays.fill(prevIndex, -1);
            subsetSize[0] = 1;
            prevIndex[0] = -1;
            for (int i = 1; i < nums.length; i++) {
                int maxSubsetSize = 0;
                int maxIndex = -1;
                for (int j = i - 1; j >= 0; j--) {
                    if (nums[i] % nums[j] == 0 && subsetSize[j] + 1 > maxSubsetSize) {
                        maxSubsetSize = subsetSize[j] + 1;
                        maxIndex = j;
                    }
                }
                subsetSize[i] = maxSubsetSize;
                prevIndex[i] = maxIndex;
            }
            int maxIndex = nums.length - 1;
            int maxSize = subsetSize[maxIndex];
            for (int j = maxIndex - 1; j >= 0; j--) {
                if (maxSize < subsetSize[j]) {
                    maxIndex = j;
                    maxSize = subsetSize[j];
                }
            }
            List<Integer> result = new ArrayList<>();
            for (int i = maxIndex; i != -1; i = prevIndex[i])
                result.add(nums[i]);
            return result;
        }
    }
    

Log in to reply
 

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