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.
Example 1:
Input: 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.
给定一个数n，要求把其拆分成至少两个数的和，使得他们的乘积最大。 数学题，没啥思路，参考网上题解。 把0~10的结果先列出来找找规律：
- 0：0
- 1：0
- 2：1=1*1
- 3：2=2*1
- 4：4=2*2
- 5：6=3*2
- 6：9=3*3
- 7：12=3*4
- 8：18=3*3*2
- 9：27=3*3*3
- 10：36=3*3*4
可以发现，n从5开始，都至少分解出来一个3，可以推断的是，当n=11时，在10的基础上，把最后一个4改成5，然后5又可以分解成3*2，所以11=3+3+3+2使得乘积最大。 4只能分解出2+2，1+3的乘积是3小于2*2；5可以分解出3+2，所以也有3。也就是说，当n大于4时，不断分解出3来，直到剩余的数小于4为止。所以有如下代码：
class Solution {
public:
int integerBreak(int n)
{
if (n <= 3)
return n – 1;
int ans = 1;
while (n > 4) {
ans *= 3;
n -= 3;
}
return ans * n;
}
};本代码提交AC，用时0MS。
再次观察上述规律，n=10的结果是n=7=10-3的结果乘以3；n=9的结果也是n=6=9-3的结果乘以3。可以推断，n的结果是(n-3)的结果乘以3。所以先列出前几个结果，后面的结果通过其前3的结果乘以3推导得到。代码如下：
class Solution {
public:
int integerBreak(int n)
{
vector<int> dp = { 0, 0, 1, 2, 4, 6, 9 };
for (int i = 7; i <= n; ++i)
dp.push_back(dp[i – 3] * 3);
return dp[n];
}
};本代码提交AC，用时3MS。