2021/4/23 最大整除子集

题目描述

描述转载自力扣《368. 最大整除子集》

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

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

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

示例1

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

示例2

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

解题思路

1. 整除关系具有传递性，若 A 可以整除 B，B 可以整除 C，那么 A 就可以整除 C，为了方便，我们需要先将数组进行排序；
2. 用动态规划的思想去解题，假设 dp[i] 意思是 “以 nums[i] 结尾的最大整除子集长度”，那么状态转移方程就是
   
   但需要满足条件
   
3. 用 maxSize 记录最大长度，用 maxVal 记录最大整除子集的最后一个元素。maxSize 的作用是方便遍历 dp 数组找到对应子集的值，而 maxVal 的作用是当从后往前遍历 dp 数组时，能够知道当前遍历到的值是否能被 maxVal 整除，若能整除，说明是子集中的数。

Java代码实现

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int maxSize = 1;
        int maxVal = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            for (int j = 0; j < i; ++j) {
                int cur = dp[j] + 1;
                if (nums[i] % nums[j] == 0 && dp[i] < cur) dp[i] = cur;
            }
            if (maxSize < dp[i]) {
                maxSize = dp[i];
                maxVal = nums[i];
            }
        }

        List<Integer> list = new ArrayList<>();
        if (maxSize == 1) {
            list.add(nums[0]);
            return list;
        }

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

}