题目
给定一个正整数n ，将其拆分为k个正整数的和（ k>= 2 ），并使这些整数的乘积最大化。
返回你可以获得的最大乘积。
示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
2 <= n <= 58
定理
我们给出一个定理：任何整数都可以被拆分为有限个2与3的和，使得拆分后的各项乘积最大。
证明：
要使拆分后的乘积达到最大，首先，1不用拆分；其次，我们不能拆分2和3，这是因为:$$2=1+1, 1 · 1 = 1 < 2$$ $$3=1+2, 1 · 2 = 2 < 3$$
再者，对于4而言，拆与不拆是等价的。
下面证明当\(n \ge 4\) 时，上述定理也成立。
先证明当\(n \ge 5\) 时，存在有效拆分方案。
给定一个常数 \(n\) ，不妨设 \(n = x + y\)，则 \(y = n - x\)，令 \(f(x)=xy-n=x(n-x)-n\).
当 \(f(x) > 0\) 时，说明拆分后获得的乘积更大，我们称这样的拆分为有效拆分.
\(f'(x)=n-2x\)，令 \(f'(x)=0\)，则 \(x=\frac{n}{2}\). 对 \(f(x)\) 求二阶导可知 \(x=\frac{n}{2}\) 是一个极大值点。
事实上，\(x\) 是离散的，因此讨论 \(f\) 的最大值应分情况讨论：
1.当 \(n\) 为偶数，则 \(f(\frac{n}{2})=\frac{n^2}{4}-n\)，令\(f(\frac{n}{2})>0\)，得\(n > 4\)
2.当 \(n\) 为奇数，则 \(max(f(x))=max(f(\frac{n-1}{2}),f(\frac{n+1}{2}))=\frac{n^2-4n-1}{4}\)，同理解得 \(n > 2 + \sqrt5\)，即\(n \ge 5\)
综上，当 \(n \ge 5\)，存在有效拆分的方案。
再证明 \(n \ge 4\) 时，\(n\)可被拆分为多个2与3的和，且拆分后各项乘积最大。
证明：
给定常数 \(n\) ,其中一个有效拆分方案获得的 \(x\) 和 \(y\)， 若二者至少有一满足大于等于4，则还可以进一步拆分，因此，不难得出最终得到的拆分项为1、2、3.
又知 \(f(1)=f(n-1) <0\)，显然拆分为1和 n-1 不是有效方案. 容易证明可以将多个1合并，或者将1与3组合成两个2达到使最后的拆分项均为2和3.
令\(n=2a+3b\)，则\(h(a)= 2^a3^b=2^a3^{\frac{n-2a}{3}}\), $h'(a) < 0 $ 恒成立，因此\(a\)越小，得到的函数值越大，即拆分时优先拆分为3获得的乘积最大.
题解
现在回到题目，题目说要将一个n拆分为k个数（k>=2），则最优拆分方案为：
1.若n=2，则ans=1
2.若n=3，则ans=2
3.若n=4，则ans=4
3.若n>=5， 则将n拆分为若干项2和3，且优先拆分为3
代码如下：
class Solution {
public:
int integerBreak(int n) {
if(n == 2)
return 1;
if(n == 3)
return 2;
if(n == 4)
return 4;
int ans = 1;
vector<int> num;
do
{
n -= 3;
num.push_back(3);
}while(n >= 5);
//最后一次迭代时，n可能为2或3或4
if(n == 2)
{
num.push_back(2);
n -= 2;
}
else if(n == 3)
{
num.push_back(3);
n -= 3;
}
else if(n == 4)
{
num.push_back(4);
n -= 4;
}
for(unsigned int i = 0; i < num.size(); i++)
ans *= num[i];
return ans;
}
};