LargestSubset.java

public List<Integer> largestDivisibleSubset(int[] nums) {
    Arrays.sort(nums);
    int maxSubsetLength = 0;
    int maxSubsetLengthStartIndex = 0;
    int[] dp = new int[nums.length];
    int[] parent = new int[nums.length]; // to keep track of the subset forming a chain
                                         // Useful concept for other problems as well.
    for(int i = nums.length - 1 ; i >= 0; i--) {
        parent[i] = i;
        for(int j = i; j < nums.length; j++) {
            if(nums[j] % nums[i] == 0 && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
                if(dp[i] > maxSubsetLength) {
                    maxSubsetLength = dp[i];
                    maxSubsetLengthStartIndex = i;
                }
            }
        }
    }
    List<Integer> result = new ArrayList<>();
    while(maxSubsetLengthStartIndex < nums.length) {
        result.add(nums[maxSubsetLengthStartIndex]);
        if(maxSubsetLengthStartIndex == parent[maxSubsetLengthStartIndex]) break;
        maxSubsetLengthStartIndex = parent[maxSubsetLengthStartIndex];
    }
    return result;
}