Golang | Leetcode Golang题解之第368题最大整除子集

本文主要是介绍Golang | Leetcode Golang题解之第368题最大整除子集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

题解：

func largestDivisibleSubset(nums []int) (res []int) {sort.Ints(nums)// 第 1 步：动态规划找出最大子集的个数、最大子集中的最大整数n := len(nums)dp := make([]int, n)for i := range dp {dp[i] = 1}maxSize, maxVal := 1, 1for i := 1; i < n; i++ {for j, v := range nums[:i] {if nums[i]%v == 0 && dp[j]+1 > dp[i] {dp[i] = dp[j] + 1}}if dp[i] > maxSize {maxSize, maxVal = dp[i], nums[i]}}if maxSize == 1 {return []int{nums[0]}}// 第 2 步：倒推获得最大子集for i := n - 1; i >= 0 && maxSize > 0; i-- {if dp[i] == maxSize && maxVal%nums[i] == 0 {res = append(res, nums[i])maxVal = nums[i]maxSize--}}return
}

这篇关于Golang | Leetcode Golang题解之第368题最大整除子集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---