leetcode-go/leetcode/medium/368.largest-divisible-subset.go

func largestDivisibleSubset(nums []int) (res []int) {
	n := len(nums)
	if n <= 1 {
		return nums
	}
	sort.Sort(sort.Reverse(sort.IntSlice(nums)))
	dp, adj := make([]int, n), make([]int, n)
	for i := 0; i < n; i++ {
		dp[i], adj[i] = 1, -1
	}
	max, idx := 0, 0
	for i := 1; i < n; i++ { // DP + math
		for j := 0; j < i; j++ {
			if nums[j]%nums[i] != 0 {
				continue
			}
			if dp[i] < dp[j]+1 {
				dp[i], adj[i] = dp[j]+1, j
			}
			if max < dp[i] {
				max, idx = dp[i], i
			}
		}
	}
	for adj[idx] != -1 {
		res = append(res, nums[idx])
		idx = adj[idx]
	}
	return append(res, nums[idx])
}