LeetCode/go/largest-divisible-subset.go

package main

import "slices"

func largestDivisibleSubset(nums []int) []int {
	slices.Sort(nums)

	dp, prev := make([]int, len(nums)), make([]int, len(nums))
	for i, _ := range nums {
		dp[i] = 1
		prev[i] = -1
	}

	maxi := 0
	for i, x := range nums {
		for j, y := range nums {
			if j >= i {
				break
			}

			if x%y == 0 && dp[i] < dp[j]+1 {
				dp[i] = dp[j] + 1
				prev[i] = j
			}
		}

		if dp[i] > dp[maxi] {
			maxi = i
		}
	}

	// reconstruct the resulting subset
	subset := make([]int, 0)
	for i := maxi; i >= 0; i = prev[i] {
		subset = append(subset, nums[i])
	}

	return subset
}