## 题目描述：

LeetCode 343. 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, 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.

Hint:

1. There is a simple O(n) solution to this problem.
2. You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

## 题目大意：

1. 题目存在O(n)的解法。
2. 你可以通过演算n为7到10的整数来寻找规律。

## 解题思路：

```7  -> 3 * 4     -> 12
8  -> 2 * 3 * 3 -> 18
9  -> 3 * 3 * 3 -> 27
10 -> 3 * 3 * 4 -> 36```

## Python代码：

``````class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
return max([reduce(operator.mul, self.splitInt(n, m)) for m in range(2, n + 1)])

def splitInt(self, n, m):
quotient = n / m
remainder = n % m
return [quotient] * (m - remainder) + [quotient + 1] * remainder
``````

## Python代码：

``````class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
return max([self.mulSplitInt(n, m) for m in range(2, n + 1)])

def mulSplitInt(self, n, m):
quotient = n / m
remainder = n % m
return quotient ** (m - remainder) * (quotient + 1) ** remainder
``````

```2  ->  1 * 1
3  ->  2 * 1
4  ->  2 * 2
5  ->  3 * 2
6  ->  3 * 3
7  ->  3 * 2 * 2
8  ->  3 * 3 * 2
9  ->  3 * 3 * 3
10 ->  3 * 3 * 2 * 2
11 ->  3 * 3 * 3 * 2
12 ->  3 * 3 * 3 * 3
13 ->  3 * 3 * 3 * 2 * 2```

```n / 3 <= 1 时，分为两个数的乘积，尽量均摊
n / 3 > 1 时，分为若干个3和2的乘积
n % 3 == 0 时，分为n个3的乘积
n % 3 == 1 时，分为n-1个3和两个2的乘积
n % 3 == 2 时，分为n个3和一个2的乘积```

## Python代码：

``````class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
div = n / 3
if div <= 1:
return (n / 2) * (n / 2 + n % 2)
mod = n % 3
if mod == 0:
return 3 ** div
elif mod == 1:
return 3 ** (div - 1) * 4
elif mod == 2:
return 3 ** div * 2
``````

dp[i]表示整数i拆分可以得到的最大乘积，则dp[i]只与dp[i - 2], dp[i - 3]两个状态有关

`dp[x] = max(3 * dp[x - 3], 2 * dp[x - 2])`

## Python代码：

``````class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 3: return n - 1
dp = [0] * (n + 1)
dp[2], dp[3] = 2, 3
for x in range(4, n + 1):
dp[x] = max(3 * dp[x - 3], 2 * dp[x - 2])
return dp[n]
``````

Pingbacks已关闭。

1. Lost_in_ 发布于 2016年4月22日 09:24 #

刚好做了这道题。
2->1*1
3->2*1
4->2*2
5->3*2
6->3*3
7->3*2*2
8->3*3*2
9->3*3*3
10->3*3*2*2
11->3*3*3*2
12->3*3*3*3
13->3*3*3*2*2
从上面可以看出，n/3<=1时,可分为两个数的乘积，尽量均摊；n/3>1时，可分为若干个3和2的乘积，n%3==0时刚好分为n个3的乘积，n%3==1时分为n-1个3和两个2的乘积，n%3==2时分为n个3和一个2的乘积。这样是不是O(1)时间复杂度，博主可以参考一下。没有找到把两个条件统一起来的规律啊....
class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
div = n / 3
if div > 1:
mod = n % 3
if mod == 0:
return 3 ** div
elif mod == 1:
return 3 ** (div - 1) * 4
elif mod == 2:
return 3 ** div * 2
else:
return (n / 2) * (n / 2 + n % 2)

2. 在线疯狂 发布于 2016年4月22日 10:36 #

感谢补充！已将你的解法添加至博文。:D

3. hellman 发布于 2016年6月23日 09:21 #

如何证明呢？怎么感觉经验看到的都不靠谱啊

4. 在线疯狂 发布于 2016年6月23日 10:41 #

数学证明可以参考LeetCode Discuss: https://leetcode.com/discuss/98276/why-factor-2-or-3-the-math-behind-this-problem