今天和大家聊的问题叫做 最大整除子集，我们先来看题面：https://leetcode-cn.com/problems/largest-divisible-subset/
Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:
answer[i] % answer[j] == 0, or
answer[j] % answer[i] == 0
If there are multiple solutions, return any of them.
给你一个由 无重复 正整数组成的集合 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]
解题
动态规划的思路，要求出最大整除的子集，首先拆分问题，从一个最小的子集再扩大为最大的子集，假设有一个最小整除子集[a,b]（a<b）则满足是b倍数的整数同样满足整除条件，此时子集被扩大为[a,b,c]（c为b的倍数），以此类推，由此得出的dp数组为1,2,3例如 [2,4,7,8,9,12,16,18] 在该题的dp数组为[1, 2, 1, 3,1, 3, 4, 2]
class Solution { public List<Integer> largestDivisibleSubset(int[] nums) { int len = nums.length; Arrays.sort(nums); // 第 1 步：动态规划找出最大子集的个数、最大子集中的最大整数 int[] dp = new int[len]; Arrays.fill(dp, 1); int maxSize = 1; int maxVal = dp[0]; for (int i = 1; i < len; 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]; maxVal = nums[i]; } } // 第 2 步：倒推获得最大子集 List<Integer> res = new ArrayList<Integer>(); 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]); maxVal = nums[i]; maxSize--; } } return res; } }
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
