未分類

Integer Break

DynamicProgramming, Go, LeetCode, Math

Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example:

1
Given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note:

You may assume that n is not less than 2 and not larger than 58.

提示 解題應用
Math 規律觀查

Default:

1
2
3
func integerBreak(n int) int {
}

解答思路:

這題有關解法主要有兩個結論:

  1. 最大值的因數必是由2與3所組成
  2. 3 3 > 2 2 * 2 同樣是6的情況下，3的乘積會比2大，因此以找出最多3的因數為主 (n>4)

至於這個結論是怎麼來的可以參考該題討論有相關的舉例與證明，唯一要注意上述第二點的情況是n需要大於4，因為4是例外而且最大值的因數也不會包含1: 2 2 > 1 3

程式碼解說:

一開始先初始化暫存值為1以用來儲存乘積的最大值，接著判斷如果n為2就回傳1(1+1)，n為3就回傳2(1+2)，而如果n大於4則利用一迴圈找出該數最多能有多少個3來做為乘積的因數，並同時記得每次都要將n減去3直到n小於等於4為止，最後乘積的暫存值與剩餘的n相乘就會是我們要的結果

1
2
3
4
5
6
7
8
9
10
11
tmp := 1
if n == 2 {
	return 1
} else if n == 3 {
	return 2
}
for n > 4 {
	tmp *= 3
	n -= 3
}
return tmp * n

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
func integerBreak(n int) int {
	tmp := 1
	if n == 2 {
		return 1
	} else if n == 3 {
		return 2
	}
	for n > 4 {
		tmp *= 3
		n -= 3
	}
	return tmp * n
}

總結:

某數由數個數字加總而來，要找出這些數字乘積的最大值，其解法最主要有兩個結論:

  1. 最大值的因數必是由2與3所組成
  2. 3 3 > 2 2 * 2 同樣是6的情況下，3的乘積會比2大，因此以找出最多3的因數為主 (n>4)
分享到