最大整除子集

368. 最大整除子集

给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：

answer[i] % answer[j] == 0 ，或
answer[j] % answer[i] == 0

如果存在多个有效解子集，返回其中任何一个均可。

示例 1：

1
2
3

输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

示例 2：

1 2	输入：nums = [1,2,4,8] 输出：[1,2,4,8]

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 109
nums 中的所有整数 互不相同

方法一：动态规划

求最大整除子集的长度

我们首先将输入数组按照升序排序，以便获得一个子集的最小整数或最大整数。dp[i] 定义为：以nums[i] 为最大整数的有序整除子集的数字个数，nums[i] 必须被选择。

从小到大计算 dp 数组的值，在计算 dp[i] 之前，我们已经计算出 dp[0 … i - 1]的值，状态转移方程为：
$$
dp[i] = max(dp[j]) + 1, 其中 0 \leq j<i 且\ nums[i]\ %\ nums[j] == 0
$$
最大整除子集长度就是 dp 数组中的最大值。

在遍历过程中我们保存最大整除子集的长度 maxSize 和子集中的最大数字 maxVal。

倒序找出最大整除子集

假设输入数组为[2,4,7,8,9,12,16,18](已经有序)，得到的动态规划表格如下：

nums	2	4	7	8	9	12	16	18
dp	1	2	1	3	1	3	4	3

初始时 maxSize = 4, maxVal = 16
寻找大小为 3 的最大整除子集，我们看到 8 和 12 对应的状态值都是 3，但 16 % 12 != 0，我们选择包含 8 的最大整除子集，此时maxSize = 3, maxVal = 8
继续向左寻找大小为 2 的最大整除子集，只有 4 对应的状态值为 2 ，选择包含 4 的最大整除子集，此时maxSize = 2, maxVal = 4
继续向左寻找大小为 1 的最大整除子集，2 对应的状态值为 1 ，选择包含 2 的最大整除子集，此时maxSize = 1, maxVal = 2

我们就得到最大整除子集[16,8,4,2]。

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);

        //动态规划找出最大子集的个数、最大子集中的最大整数
        int[] dp = new int[len];
        dp[0] = 1;
        int maxSize = 1;
        int maxVal = nums[0];
        for(int i = 1; i < len; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] % nums[j] == 0){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            if(dp[i] > maxSize){
                maxSize = dp[i];
                maxVal = nums[i];
            }
        }

        //倒推获得最大子集
        List<Integer> res = new ArrayList<>();
        if(maxSize == 1){
            res.add(nums[0]);
            return res;
        }

        for(int i = len - 1; i >= 0 && maxSize > 0; i--){
            if(dp[i] == maxSize && maxVal % nums[i] == 0){
                res.add(nums[i]);
                maxSize--;
                maxVal = nums[i];
            }
        }
        return res;
    }
}

时间复杂度O(n^2)
空间复杂度O(n)

当前问题和使用动态规划解决的经典问题「300. 最长递增子序列」有相似之处。