29-line clear java DP solution


  • 0
    2
    public class Solution {
        public List<Integer> largestDivisibleSubset(int[] nums) {
    		LinkedList<Integer> ret = new LinkedList<Integer>();
    		int len = nums.length;
    		if (len == 0) {
    			return ret;
    		}		
    		Arrays.sort(nums);
    		int[] f = new int[len];
    		int[] pre = new int[len];
    		int pos = 0;		
    		for (int i = 0; i < len; i ++) {			
    			f[i] = 1;
    			pre[i] = -1;
    			for (int j = 0; j < i; j ++) {
    				if (nums[i] % nums[j] == 0 && f[j] + 1 > f[i]) {
    					f[i] = f[j] + 1;
    					pre[i] = j;					
    				}
    			}
    			pos = f[pos] < f[i] ? i : pos;
    		}
    		while (pos != -1) {
    			ret.addFirst(nums[pos]);
    			pos = pre[pos];
    		}
    		return ret;		
        }
    }
    

  • 0
    W

    Very good answer.I rewrote your code,just 13 lines.

    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        Arrays.sort(nums);
        int[] count = new int[nums.length], parents = new int[nums.length];
        int maxIdx = 0;
        for (int i = 0, j; i < nums.length; maxIdx = count[i] > count[maxIdx] ? i : maxIdx, i++)
            for (j = 0, count[i] = 1, parents[i] = -1; j < i; j++)
                if (nums[i] % nums[j] == 0 && count[j] + 1 > count[i]) {
                    count[i] = count[j] + 1;
                    parents[i] = j;
                }
        for (; maxIdx != -1; maxIdx = parents[maxIdx])
            result.add(nums[maxIdx]);
        return result;
    }

Log in to reply
 

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