package main

import (
	"fmt"
	"sort"
)

func largestDivisibleSubset(num []int) (res []int) {
	sort.Ints(num)
	n := len(num)
	maxIdx, maxLen, dp := 0, 0, make([][2]int, n, n)
	dp[0] = [2]int{1,0}
	for i := 1 ; i < n ; i++ {
		// 如果找不到可以合并的区间，就自己单独作为一个区间
		dp[i] = [2]int{1,i}
		subMaxLen := 0
		for j := i - 1 ; j >= 0 ; j -- {
			if num[i] % num[j] == 0 || num[j] % num[i] == 0 {
				newLen := dp[j][0] + 1
				if newLen > subMaxLen {
					dp[i] = [2]int{newLen , j}
					subMaxLen = newLen
					if newLen > maxLen {
						maxLen = newLen
						maxIdx = i
					}
				}
			}
		}
	}
	// 从头maxIdx开始填充res
	for dp[maxIdx][1] != maxIdx {
		res = append(res, num[maxIdx])
		maxIdx = dp[maxIdx][1]
	}
	res = append(res, num[maxIdx])
	return res
}

func main() {
	fmt.Println(largestDivisibleSubset([]int{4,8,10,240}))
}