LeetCode 368 Largest Divisible Subset

LeetCode 368 Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (S_i, S_j) of elements in this subset satisfies:

S_i % S_j = 0 or S_j % S_i = 0.

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

Example 1:

**Input:** [1,2,3]
**Output:** [1,2] (of course, [1,3] will also be ok)

Example 2:

**Input:** [1,2,4,8]
**Output:** [1,2,4,8]

题目大意：

一个数组，让我们求这样一个子集合，集合中的任意两个数相互取余均为0。

解题思路：

由于知道子问题有助于求解考虑用DP。它就是LIS的翻版。这道题还需要打印DP路径。

1. 定义dp[i]为num[i-1]这个数对应的最大可整除子集合个数。
2. 递归式为dp[i] = max{dp[j-1] + 1}, 0<j<i, 若num[i-1]可被num[j-1]整除
3. 方向为从左到右。初始值为dp = 1。
4. path数组记录解的下标+1，每求得一个解dp[i] = dp[j] + 1就记录对应上一层解的下标，也就是到此解的路径。

注意事项：

1. 初始值dp = 1。

Java代码：

public List<Integer> largestDivisibleSubset(int[] nums) {
	List<Integer> res = new ArrayList<>();
	if(nums == null || nums.length == 0)
		return res;
	if(nums.length == 1)
		return Arrays.asList(nums[0]);
	Arrays.sort(nums);
	int max = Integer.MIN_VALUE;
	int maxPos = -1;
	int[] dp = new int[nums.length + 1];
	int[] path = new int[nums.length + 1];
	for(int i = 0; i < dp.length; i++) // remember to init to 1
		dp[i] = 1;
	for(int i = 1; i < dp.length; i++) {
		for(int j = 1; j < i; j++) {
			if(nums[i-1] % nums[j-1] == 0 && dp[j] + 1 > dp[i]) {
				dp[i] = dp[j] + 1;
				path[i] = j;
			}
		}
		if(dp[i] > max) { // the biggest value might not be the last one, keep track of the start pos for the path
			max = dp[i];
			maxPos = i;
		}
	}
	int pos = maxPos;
	for(int i = 0; i < dp[maxPos]; i++) {
		res.add(nums[pos-1]);
		pos = path[pos];
		
	}
	Collections.sort(res);
	return res;
}

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2)。