题目

给定一个正整数 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

  解题方法

  动态规划

  设定动态数组dp[i]表示数字i+1拆分后能够得到的最大乘积，则有如下递推关系：
  
  初始条件为dp[1]=1。
  时间复杂度O(n^2)，空间复杂度O(n)
  C++代码：

  class Solution {
  public:
    int integerBreak(int n) {
        vector<int> dp(n, 0);
        dp[1] = 1;
        for(int i=3; i<=n; i++) {
            for(int j=1; j<i; j++) {
                dp[i-1] = max(dp[i-1], max((i-j)*j, dp[i-j-1]*j));
            }
        }
        return dp[n-1];
    }
  };

  动态规划（优化）

  对上述递推关系，首先考虑j*dp[i-j]一项。
  当j≥4且为奇数时，有如下关系：
  
  当j≥4且为偶数时，有如下关系：
  
  当且仅当j=4时，等号成立。并且对于任意j≥4，都有：
  
  因此，仅需要考虑j=2的情况即可，对于j≥4的情况无需再考虑。由于j=3的情况无法排除，所以对于任意j≥3，都有max(2×dp[i-2],3×dp[i-3])≥j×dp[i-j]。

对于递推关系中的j*(i-j)一项，当j≥4时有

所以也只需要考虑j为2和3的情况，优化后的递推关系如下：

时间复杂度O(n)，空间复杂度O(n)
C++代码：

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1, 0);
        dp[2] = 1;
        for(int i=3; i<=n; i++) {
            dp[i] = max(max((i-2)*2, dp[i-2]*2), max((i-3)*3, dp[i-3]*3));
        }
        return dp[n];
    }
};

数学推导

函数极值证明法

定义函数f(x)表示将给定的正整数n拆分成尽可能多的正数x的情况下的最大乘积，则可以将n分成n/x项，此时

目标是求f(x)的最大值，即:

可以将f(x)写成如下形式：

令

则有f(x)=g(n⋅h(x))。由于g(t)是单调递增的，n>0，因此h(x)与f(x)的单调性相同。
计算h(x)的驻点，即

的点，得到驻点为x=e。
由于当0<x<e时h'(x)>0，当x>e时h'(x)<0，因此x=e是h(x)的极大值点，也是f(x)的极大值点。由于函数f(x)的定义域连续，因此极大值点唯一，也是最大值点。因此，当x=e时，f(x)取到最大值

由于e不是整数，因此使用与e最接近的整数作为x的值，可以是2或3，此时需要比较f(2)与f(3)的大小，可以通过计算

进行比较。

由于ln9>ln8，因此f(3)/f(2)>1，即f(3)>f(2)``f(3)>f(2)。当x=3时，可以得到最大乘积。因此，应该将给定的正整数拆分成尽可能多的3。

根据n除以3的余数进行分类讨论：

• 如果余数为0，即n=3m(m≥2)，则将n拆分成m个3；
• 如果余数为1，即n=3m+1(m≥1)，由于2×2>3×1，因此将n拆分成m-1个3和2个2；
• 如果余数为2，即n=3m+2(m≥1)，则将n拆分成m个3和1个2。

上述拆分的适用条件是n≥4。如果n≤3，则上述拆分不适用，需要单独处理。

• 如果n=2，则唯一的拆分方案是2=1+1，最大乘积是1×1=1；
• 如果n=3，则拆分方案有3=1+2=1+1+1，最大乘积是1×2=2。

这两种情形可以合并为：当n≤3时，最大乘积是n-1。

归纳证明法

第一步：证明最优的拆分方案中不会出现大于**4**的整数。
假设出现了大于4的整数x，由于2(x-2)>x在x>4时恒成立，将x拆分成2和x-2可以增大乘积。因此最优的拆分方案中不会出现大于4的整数。

第二步：证明最优的拆分方案中可以不出现整数**4**。
如果出现了整数4，我们可以用2×2代替之，乘积不变。此时，我们可以知道，最优的拆分方案中只会出现1，2和3。

第三步：证明当**n≥5**时，最优的拆分方案中不会出现整数**1**。
当n≥5时，如果出现了整数1，那么拆分中剩余的数的和为n−1≥4，对应这至少两个整数。我们将其中任意一个整数x加上1，乘积就会增大。因此最优的拆分方案中不会出现整数1。此时，我们可以知道，当n≥5时，最优的拆分方案中只会出现2和3。

第四步：证明当**n≥5**时，最优的拆分方案中**2**的个数不会超过**3**个。
如果出现了超过3个2，那么将它们转换成2个3，可以增大乘积，即3×3>2×2×2。
此时，n≥5的最优拆分方案就唯一了。这是因为当最优的拆分方案中2的个数分别为0，1，2个时，就对应着n除以3的余数分别为0，2，1的情况。因此我们可以得到和「函数极值证明法」相同的分类讨论结果。

时间复杂度O(1)，空间复杂度O(1)
C++代码：

class Solution {
public:
    int integerBreak(int n) {
        if(n<4) return n-1;
        int a = n/3;
        int b = n%3;
        int result = 1;
        for(int i=1; i<a; i++)   result *= 3;
        if(b==0)    return (int)(result *3);
        else if(b==1)   return (int)(result * 4);
        else            return (int)(result * 6);
    }
};