题目概述
Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers. Return the maximum product you can get.
Constraints:
2 <= n <= 58
思路
根据题意，对于一个给定的正整数 $n$ , 有:
\[n = \sum_{i=1}^k n_i \qquad (1 \leq k \leq n, \quad n_k \in \boldsymbol{Z^+})\]现在需要求:
\[max(\prod_{i=1}^k n_i)\]注意到这里的任意 $n_i$ 均为正整数，所以根据均值不等式，有：
\[\begin{aligned} \sqrt[k]{n_1 n_2 \cdots n_k} \quad &\leq \quad \frac{n_1 + n_2 + \cdots + n_k}{k} \\[5mm] n_1 n_2 \cdots n_k \quad &\leq \quad \left(\frac{n_1 + n_2 + \cdots + n_k}{k}\right) ^ k \end{aligned}\]当且仅当 $n_1 = n_2 = \cdots = n_k$ 时不等式取等号，也即乘积取得最大值。但是在这道题的语境下 $n_i$ 为正整数，直接取等的话无法保证满足这个条件。不过，我们可以先按照这个思路去求得 $k$ 取什么值，也即原本的整数 $n$ 在被均分成多少个数的时候它们的乘积能得到最大值。令:
\[f(k) = n_1 n_2 \cdots n_k = \left(\frac{n}{k}\right)^k \qquad (1 \leq k \leq n)\]想要求 $f(k)_{max}$ , 利用对数微分法求导:
\[\begin{aligned} & log f(k) = k log (\frac{n}{k}) = k (log n - log k) \\[3mm] & \frac{f'(k)}{f(k)} = (log n - log k) - \frac{1}{k} \times k = log n - log k - 1 \\[3mm] & f'(k) = \left(\frac{n}{k}\right) ^ k (log n - log k - 1) \end{aligned}\]令 $f’(k) = 0$ , 有:
\[\begin{aligned} & log n - log k - 1 = 0 \\[3mm] & log k = log n - 1 = log n - log e = log \left(\frac{n}{e}\right) \\[3mm] \therefore \quad & k = \frac{n}{e} \end{aligned}\]考察 $f(k)$ 增减性:
\[\begin{aligned} & 1 \leq k \leq \frac{n}{e} \quad , \quad f'(k) > 0 \\[3mm] & k > \frac{n}{e} \quad , \quad f'(k) < 0 \end{aligned}\]所以 $f(k)$ 在 $k = \large \frac{n}{e}$ 时取得最大值, 此时每一个乘数的值均为 $e$ 。但题目里要求乘数必须为正整数，所以这还不是最终的答案。这里虽然没有严谨的证明，但是我们可以近似地认为只要分离出的乘数 $n_i$ 越接近 $e$ , 那么最终这些乘数的乘积越大。而最接近 $e$ 的正整数为3，所以问题似乎就转变成: 将一个正整数尽可能多地分成正整数3的和。
但这样还不对。我们可以设想一下 $n = 7$ 时，如果只是尽可能多地分离出3，那么最终的结果为:
\[7 = 3 + 3 + 1 \quad , \quad 3 \times 3 \times 1 = 9\]然而我们还能得到:
\[7 = 3 + 4 \quad , \quad 3 \times 4 = 12\]显然12是大于9的。这里其实稍加思考便可以得知问题出在了哪。当我们将一个数不断地拆分为3和剩余的部分，那么根据这个数除以3得到的余数，最终会有如下三种情况:
- 余数为0, 刚好将3分离完的最理想情况，无需再做讨论。
- 余数为2, 那么最后剩余的部分为2或5 (少分离一个3), 如果考虑与 $e \approx 2.71828$ 的接近程度，那么显然前者更优。（两种分离方式在倒数第三项为止的乘积相同, 剩下要做的比较便是(2, 3)与5哪一种与 $e$ 的差值最小, 显然前者更小）
- 余数为1, 与上一种情况类似，这里最后剩余的部分为(1, 3)或(2, 2), 比较与 $e$ 的差值的话后者更优。
到这里为止，问题基本就分析完毕了。最后还需考虑一种情况，那便是 $n \leq 3$ 的时候。这里可以作为特判, 无外乎两种情况:
- 2 = 1 + 1, 结果为1
- 3 = 1 + 2, 结果为2
总结一下思路: 在$n > 4$时，尽可能多地分离出3。
代码实现
在 $n > 4$ 时，尽可能多地分离出3
Time complexity: O(n)
Space complexity: O(1)
1 2 3 4 5 6 7 8 9 10 11
class Solution: def integerBreak(self, n: int) -> int: if n <= 3: return n - 1 ans = 1 while n > 4: ans *= 3 n -= 3 return ans * n
优化, 根据 $n$ 的值直接可以计算出分离出来的3的个数, 按照其除以3的余数分类讨论即可
Time complexity: O(logn)
Space complexity: O(1)
1 2 3 4 5 6 7 8 9 10 11 12
class Solution: def integerBreak(self, n: int) -> int: if n <= 3: return n - 1 if n % 3 == 0: return 3 ** (n // 3) elif n % 3 == 1: return 3 ** ((n - 4) // 3) * 4 else: return 3 ** ((n - 2) // 3) * 2
注： 乘方运算的时间复杂度为 O(logn)
