Largest Divisible Subset - Lintcode

Given a set ofdistinct positiveintegers, find the largest subset such that every pair(Si, Sj)of elements in this subset satisfies:Si % Sj = 0orSj % Si = 0.

Notice

If there are multiple solutions, return any subset is fine.

Example

Given nums =[1,2,3], return[1,2]or[1,3]

Given nums =[1,2,4,8], return[1,2,4,8]

Analysis

The x % y == 0 condition is only possible to be valid when x > y; so we can sort the numbers ascendingly and check whether x % y == 0 with y being the smaller number . Also one important observation to make here is if x % y == 0 and y % z == 0, then x % z == 0. This means that the larger number's subset can be built on top of small numbers. An "prev" array can be used to do the tracing. Since this issue can be solved by breaking it into smaller problems. And the smaller problems's solution can be stored so that it doesn't need to be solved repeatedly. This is a DP problem.

Take away

a prev array to do the track back and how a bigger problems is broken into small problems.

public List<Integer> largestDivisibleSubset(int[] nums) {
    List<Integer> result = new ArrayList<Integer>();
    if (nums.length == 0){
        return result;
    }

    Arrays.sort(nums);
    int[] numOfSubSets = new int[nums.length];
    int[] prev = new int[nums.length];

    for (int i = 0; i < nums.length; i++){
        numOfSubSets[i] = 1;
        prev[i] = i;
        for (int j = 0; j < i; j++){
            if (nums[i] % nums[j] == 0 && numOfSubSets[i] < numOfSubSets[j] + 1){
                numOfSubSets[i] = numOfSubSets[j] + 1;
                prev[i] = j;                    
            }
        }
    }

    int max = Integer.MIN_VALUE; 
    int max_i = -1;
    for (int i = 0; i < numOfSubSets.length; i++){
        if (numOfSubSets[i] > max){
            max = numOfSubSets[i];
            max_i = i;
        }
    }

    result.add(nums[max_i]);
    while(prev[max_i] != max_i){
        max_i = prev[max_i];
        result.add(nums[max_i]);
    }

    Collections.reverse(result);
    return result;        
}