# 整数拆解
# 343. 整数拆分 (opens new window)
难度中等221收藏分享切换为英文关注反馈
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
1
2
3
2
3
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
1
2
3
2
3
说明: 你可以假设 n 不小于 2 且不大于 58。
# 1、规律推导（不太严谨，在没有办法时或快速求解时用这个方法求解）
第一步先列举出前面几个数的解，列举到大概能看出规律为止
然后总结规律
最后挑选几个值验证下规律是否正确
0 0
1 0
2 1+1 1
3 1+2 2
4 2+2 4
5 2+3 6
6 3+3 9 2+2+2 8
7 2+2+3 12
8 2+3+3 18
9 2+2+3 20
10 2+3+2+3 36
11 2+3+3+3 54
12 3+3+3+3 81
列举了下前12个，大概可看出最后拆分的都是3 ，所以最优拆解数字，余下的2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
根据规律推导出：将n/3 得到3的个数，根据n%3的余数 0,1,2来做不同的处理
当余数为0时，说明正好能拆分成 n/3个3 积就是
当余数为1时，需要拿出一个3与1整合成 4，这样积就是
3^{取整(n/3)-1}\times4当余数为2时，积为
3^{取整(n/3)}\times2代码：
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
let initArr = [0,0,1,2] //0-3的值
if(initArr[n]!==undefined) return initArr[n]
let a1 = n%3 //余数
let a3 = Math.floor(n/3) //拆分3的数量
if(a1===1){
a3--
return Math.pow(3,a3)*4
}
if(a1===2){
return Math.pow(3,a3)*2
}
if(a1===0){
return Math.pow(3,a3)
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
优化后代码
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
let initArr = [0,0,1,2]//0-3的值
if(initArr[n]!==undefined) return initArr[n]
let remainder = n%3 //余数
let num3 = Math.floor(n/3) //拆分3的数量
if(remainder===1){
return 3**(num3-1)*4
}else{
return 3**num3*remainder
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15