别人家的面试题：自然数拆分求最大乘积
今天是部门活动，去了石林峡，爬山累成狗。不过，在这么好的天气里，外出走走实在是一件有益身心健康的事情。爬山回来之后，身体虽疲惫，思路竟格外敏捷，正好将这篇文章一气呵成。
自然数拆分（Integer Break）
给定一个自然数 n (n ≥ 2），将它拆分成不少于两个自然数之和，对这些拆分后的自然数求积，要求算出最大的乘积。
例如：
- n = 2，得到 1（2 = 1 + 1）
- n = 10，得到 36（10 = 3 + 3 + 4）
解题思路
这道题，咋一看之下，比前两期的题目似乎要难一些。因为对于一个较大的自然数，存在很多种拆分方法，怎么找到乘积最大的拆分方法呢？
简单一点考虑？遍历出一个自然数 n 的所有拆分方法，然后找出乘积最大的那个？ 这么做当然可行，但看起来这似乎不像是什么好办法。有没有突破点呢？同样按照惯例，大家先思考30秒钟再往下看----
寻找规律
你是不是心里猜到了什么？是不是"那样"的方法能得到最大乘积？先别着急，我们来找一些数寻找一下规律，下面列出从 2 到 10 的所有结果：
- 2 = 1 + 1 -> 1
- 3 = 2 + 1 -> 2
- 4 = 2 + 2 -> 4
- 5 = 3 + 2 -> 6
- 6 = 3 + 3 -> 9
- 7 = 3 + 2 + 2 -> 12
- 8 = 3 + 3 + 2 -> 18
- 9 = 3 + 3 + 3 -> 27
- 10 = 3 + 3 + 2 + 2 -> 36
从上面是不是发现了什么规律？我想这对我们来说应该不难----
月影猜想：
- 对任意自然数 n （n > 3）要拆解得到最大乘积，该拆解方案不包含大于3的数（这里附加一个规则，假定我们总是把"4"拆成"2+2"，因为不影响乘积大小）。
- 并且这个拆解方案中 2 出现的次数少于 3 次。
证明猜想
让我们从数学上证明"月影猜想"，这并不难，第一步让我们先复习一下自然数的一些小的基本性质。
定理： 任意两个不小于 2 的自然数 a、b，有 a + b ≤ a * b。
上面这个定理不难证明：假设 2 ≤ a ≤ b，那么有 a + b ≤ b + b ≤ 2 b ≤ a b
因此，从上面的定理得到----
推论：对于任意自然数 n， n ≥ 4，必然存在一个自然数拆分，将 n 拆分成两个自然数 a 和 b，使得 a * b ≥ n。
根据上面的推论我们可以证明猜想的"1."即最大乘积的拆解方案中不包含 大于 3 的数。
接着，我们可以通过反证法证明如果拆解方案包含的 2 不少于 3 次，就不是乘积最大的拆解方案：
假设自然数 n 的乘积最大拆解方案是： n = 3 + …… \+ 2 + 2 + 2 它的乘积是 m = 3 * …… * 2 * 2 * 2 = (3 * ……) * 8，那么我们用 3 + 3 替换掉最后的 2 + 2 + 2，它的乘积 m' = 3 * …… * 3 * 3 = (3 * ……) *9，显然 m' > m，因此 m' 是比 m 乘积更大的拆解方案，所以 m 不是乘积最大的拆解方案，于是我们证明了猜想的"2."即拆解方案中 2 出现的次数少于 3 次，也是正确的。
以上证明了"月影猜想"的正确性，于是我们可以进一步推导出 n 拆解后最大乘积的通项公式：
- f(2) = 1
- f(3) = 2
- f(3k) = 3k (k ≥ 2)
- f(3k+1) = 2 2 3k-1 (k ≥ 1)
- f(3k+2) = 2 * 3k (k ≥ 1)
所以，我们得到了这个问题的简单解法，它的时间和空间复杂度是 O(1)：
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
if(n < 3) return 1;
if(n === 3) return 2;
var k = Math.floor(n / 3);
var r = n % 3;
if(r === 0) return Math.pow(3, k);
else if(r === 1) return 4 * Math.pow(3, k - 1);
else return 2 * Math.pow(3, k);
};
以上就是月影的解题思路，注意中间的数学证明和推导过程。我们当然可以只通过找规律来建立通项公式，忽略推导内容，一样可以把这道题解出来。然而月影一直以来认为：只有经过数学证明的模型才是完美的，才经得起考验，而这些证明并不困难，不需要多么高深的数学知识。不管是做前端还是其他软件开发领域，数学，对我们都是非常重要的。
以上是 leetcode 算法面试系列的第三期，在下一期里，我们讨论另外一道考验算法效率的题目。这道题看似非常简单----给一个数值数组 NumArray，能够快速求出 sumRange(i, j)，即从第 i 个元素到第 j 个元素中间的所有元素之和。似乎没有什么值得思考的，然而如果数组非常大，sumRange被执行次数非常多，我们又如何来做优化呢？大家可以想一想，期待我们的下一期。
对于本期和下一期的问题，有任何想法，欢迎留言讨论~~