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.

Example 1:

nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

nums: [1,2,4,8]

Result: [1,2,4,8]

解法1：

思路是：
if a < b then a % b != 0 for all a , b > 0
所以只需要对与一个数，只要从大往小找小于他的数即可。
第二步：
先把数组排序，便于分析。
对于排好序的数组，我们可以计算出对于每一个数字，数组中存在的可以整除他的数的最大个数。
这可以用一个dp完成。
统计出最大的个数的同时，如果我们维护另外一个数组，记录能被整除且sequence最长的那个数的index，就能在之后把整条链提取出来。

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        Arrays.sort(nums);          // sort the array first
        int n = nums.length;
        int[] dp = new int[n];
        int[] index = new int[n];   // index stores the corresponding next item in the longest subsequence
        Arrays.fill(dp, 1);
        Arrays.fill(index, -1);
        int max = 1;
        int maxIndex = 0;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;  // update the dp array
                        index[i] = j;
                    }
                }
            }
            if (dp[i] > max) {
                max = dp[i];
                maxIndex = i;
            }
        }
        // maxIndex
        for (int i = maxIndex; i != -1; i = index[i]) {
            res.add(nums[i]);
        }
        return res;
    }
}

这题如果改成，求最长的subset的长度，使得subset中每两个数字都能保证其中一个被整除，那么这就是一个经典的dp问题。
这题的难点是在这个的基础上要求出这个subset。对于这种问题，一般可以采取的方法就是在dp的过程中记录下每一个点的optimal解法相对应的位置。
这题就是这样，dp[i]记录下对于第i个点，他们之前的0到i-1个点对应的能被其整除的数字的个数，当这个个数被更新的时候，记录下其所对应的位置。
当扫描结束一遍之后，我们也得到了对应于最大答案的subset中每一个点的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int n = nums.length;
        Arrays.sort(nums);
        int[] dp = new int[n];  // stores the number of longest subsequence of the array that all elements can be divisible
        dp[0] = 1;
        int[] tracks = new int[n];
        Arrays.fill(tracks, -1);
        int max = 0;
        for (int i =1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (dp[j] + 1 >= dp[i]) {
                        dp[i] = dp[j] + 1;
                        tracks[i] = j;
                    }
                }
            }
            if (dp[i] >= dp[max]) {
                max = i;
            }
        }
        // start from i and trace back to get the list
        for (int i = max; i >= 0; i = tracks[i]) {
            res.add(nums[i]);
        }
        return res;
    }
}