DP java solution : Time O(n ^ 2) Space : O(n)


  • 0
    N
    public List<Integer> largestDivisibleSubset(int[] array) {
    	if (array == null || array.length == 0) {
    	      return new ArrayList<Integer>();
        }
        Arrays.sort(array);
    	int[] prev = new int[array.length];
    	for(int i = 0; i < prev.length; i++) {
    	    prev[i] = i;
    	}
    	int[] M = new int[array.length];
    	int max = 1, maxIndex = 0;
    	Arrays.fill(M,1);
    	for (int i = 1; i < array.length; i++) {
       		for (int j = 0; j < i; j++) {
                if ((array[i] % array[j] == 0)  || (array[j] % array[i] == 0)){
            		M[i] = Math.max(M[j] + 1, M[i]);
            		if (M[i] == M[j] + 1) {
            		    prev[i] = j;
            		}
                }
            }
            max = Math.max(M[i], max);
            maxIndex = max == M[i] ? i : maxIndex;
        }
        
    	return construct(array,prev,M,maxIndex);
    }
    
    public List<Integer> construct (int[] array, int[] prev, int [] M, int index) {
        LinkedList<Integer> res = new LinkedList<>();
        int count = M[index];
        while (count > 0) {
        	res.addFirst(array[index]);
        	index = prev[index];
        	count--;
        }
        return res;
    }
    

    }


Log in to reply
 

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