# 343.整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
官方给的例子：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
1
2
3
2
3
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
1
2
3
2
3
# 思路
1.根据官方的提示，可以观察7-10的规律。
输入：7
可以拆分成 4+3=7 4*3=12 ; 3+3+1=7 3*3*1=9 ; 2+2+2+1=7 2*2*2*1=8 ;2+2+3=7 2*2*3=12
最高组合为; 4+3 2+2+3 12
输入; 8
拆分:4+4 , 16 ; 5+3 ,15 ; 2+2+2+2+2 ,16 ; 3+2+2+1 12 ; 3+3+2 18
最高为 3+3+2
9 ： 3+3+3 , 27 ; 6+3 18;
10: 3+3+4,36 ,3+3+2+2 36;
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
发现，最大值组成为3，2的组合。因此把整数拆分成最多3，和2的组合,同时需要避免出现1
2.证明，3和2组合为最大的乘积。
设整数N可以拆分成 ： $ a_1+a_2 +a_3+...+a_n $ 那么最大值为： $ \max(a_1*a_2 * a_3 * ... * a_n) $
由均值不等式。 $ \frac {a_1+a_2 +a_3+...+a_n} {n} \geqslant \sqrt[n]{a_1a_2a_3...a_n} $