gistfile1.go

// お題：n個の任意の自然数の和がxのとき、n個の自然数の積の最大値を求める。
// 例
// x=10 -> 36
// x=64 -> 13947137604
// x=100 -> 7412080755407364

package main
import ("fmt")

func calc(N int) uint64 {
	var max uint64
	var dp []uint64
	dp = make([]uint64, N + 1)
	dp[1] = 1
	for i := 2; i <= N; i++ {
		max = 1
		for j := 1; j < i; j++ {
			if (max < dp[i - j] * dp[j]) {
				max = dp[i - j] * dp[j]
			}
		}
		if max > uint64(i) {dp[i] = max} else {dp[i] = uint64(i)}
	}
	return dp[N]
}

func main() {
	fmt.Println(calc(1)) // -> 36 
	fmt.Println(calc(64)) // -> 13947137604 
	fmt.Println(calc(100)) // -> 7412080755407364 
}