Largest Divisible Subset

LeetCode Q 368 - Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0

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

Solution

We can solve this problem following these four steps:

1. Sort
2. Find the length of longest subset
3. Record the largest element of it.
4. Do a loop from the largest element to nums[0], add every element belongs to the longest subset.

Code:

public List<Integer> largestDivisibleSubset(int[] nums) {
	List<Integer> res = new ArrayList<>();
	if (nums == null || nums.length == 0)
		return res;
	// 1. sort
	Arrays.sort(nums);

	// 2. Find the length of longest subset
	int[] dp = new int[nums.length]; // records the number of each subset contains i
	Arrays.fill(dp, 1);
	for (int i = 1; i < nums.length; i++) {
		for (int j = 0; j < i; j++) 
			if (nums[i] % nums[j] == 0) dp[i] = Math.max(dp[i], dp[j] + 1);
	}

	// 3. Record the largest element of it.
	int maxIndex = 0;
	for (int i = 0; i < nums.length; i++) {
		if (dp[i] >= dp[maxIndex])
			maxIndex = i;
	}

	// 4. Do a loop from the largest element to nums[0], add every element belongs to the longest subset. -- easily making mistake at this step
	int temp = nums[maxIndex];
	int val = dp[maxIndex];
	for (int i = maxIndex; i >= 0; i--) {
		if (val == dp[i] && temp % nums[i] == 0) {
			res.add(nums[i]);
			temp = nums[i];
			val--;
		}
	}

	return res;
}