最大整除子集

力扣 368. 最大整除子集

题目说明

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

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

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

示例

例1

1
2
3

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

例2

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

笔者理解

此题是一道动态规划算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题只需要动态规划向后依次转移出各个数之前的能被其整除的数的总和即可，用标记来标记标记最大的最大整除子集的长度和最后一个数即可，让我们来看看具体如何实现的吧。

实现

public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;

        Arrays.sort(nums);
        int[] dp = new int [n];

        Arrays.fill(dp, 1);

        // 标记最后一个数和结果集的长度
        int maxSize = 1;
        int maxNum = 0;

        // 依次遍历各个数，看此数前面有几个能够被其整除
        for (int i = 0; i < n; i++) {
            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];
                    maxNum = nums[i];
                }
            }
        }
 
        List<Integer> result = new ArrayList();
        for (int i = n - 1; i >= 0; i--) {
            // 向前寻求最大整除序列 ，因为没有重复元素，所以选择是尽可能单一的的
            if(maxSize == dp[i] && maxNum % nums[i] == 0) {
                result.add(0, nums[i]);
                maxSize--;
                maxNum = nums[i];
            }
        }

        return result;
    }