题目描述

给定一个正整数 $n$，将它拆分成最少两个数的和，使得这些数的乘积最大。请返回最大的乘积。

注意： $2 \le n \le 58$；

样例1

给定 n = 2;
输出：1
解释：2 = 1 + 1，至少表示成两个数的和；

样例2

给定 n = 10；
输出 36
解释：10 = 3 + 3 + 4；

算法

(数学) $O(n)$

这道题目是数学中一个很经典的问题。
下面我们给出证明：

首先把一个正整数 $N$ 拆分成若干正整数只有有限种拆法，所以存在最大乘积。
假设 $N = n_1 + n_2 + … + n_k$，并且 $n_1 \times n_2 \times … \times n_k$ 是最大乘积。

1. 显然1不会出现在其中；
2. 如果对于某 $i$ 有 $n_i \ge 5$，那么把 $n_i$ 拆分成 $3 + (n_i - 3)$，我们有 $3(n_i - 3) = 3n_i - 9 \gt n_i$；
3. 如果 $n_i = 4$，拆成 $2 + 2$乘积不变，所以不妨假设没有4；
4. 如果有三个以上的2，那么 $3 \times 3 \gt 2 \times 2 \times 2$，所以替换成3乘积更大；

综上，选用尽量多的3，直到剩下2或者4时，用2。

时间复杂度分析：当 $n$ 比较大时，$n$ 会被拆分成 $\lceil n / 3 \rceil$ 个数，我们需要计算这么多次减法和乘法，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    int integerBreak(int n) {
        if (n <= 3) return 1 * (n - 1);
        int res = 1;
        if (n % 3 == 1) res = 4, n -= 4;
        else if (n % 3 == 2) res = 2, n -= 2;
        while (n) res *= 3, n -= 3;
        return res;
    }
};