题目：
给一个数n，你可以将这个数拆成任意个整数之和。找出在所有的拆分方式中，拆出来的所有的数的积的最大值（也包括只拆成一个数，如2拆成2最大）。
如 n = 6, 可以拆成
3 * 3 = 9 2 * 4 = 8
2 * 2 * 2 = 8 1 * 1 * 4 = 4
1 * 1 * 2 * 2 = 4 ...
最大值为9。
3 * 3 = 9 2 * 4 = 8
2 * 2 * 2 = 8 1 * 1 * 4 = 4
1 * 1 * 2 * 2 = 4 ...
最大值为9。
分析：
比较容易想到的是使用动态规划来解该题。首先找出状态方程，可以设f(n)为n拆分后积最大的值，则f(n)=max{i*f(n-i)}, i=1,2...n-1。其中f(1)=1, f(2)=2。使用递归效率上可能会有点问题，不过也很容易改成非递归。
动态规划法代码：
//递归法
int f(int N) {
if (N == 1 || N == 2)
return N;
int max = N;
for (int i = 1; i < N; i++) {
int tmp = i * f(N - i);
if (tmp > max)
max = tmp;
}
return max;
}
如果题目改成分解的数字不能有重复，比如6不能分解为3+3，则可以参见http://blog.csdn.net/jqmczx/article/details/6400723的分析。