Given a positive integern, break it into the sum ofat leasttwo positive integers and maximize the product of those integers. Return the maximum product you can get.
For example, givenn= 2, return 1 (2 = 1 + 1); givenn= 10, return 36 (10 = 3 + 3 + 4).
Note: You may assume thatnis not less than 2 and not larger than 58.
Hint: There is a simple O(n) solution to this problem.
You may check the breaking results ofnranging from 7 to 10 to discover the regularities.
代码简单， 分析过程很有趣！
当一个数拆分成两个的时候乘积最大情况， 偶数时： n/2 * n/2 >= n , n的最小值 4； 奇数时： (n+1)/2 * (n-1)/2 >= n; n==5 , 也就是说当一个数大于等于4的时候 应该有更好的拆分方法。 所以选择因子应该在1，2，3 中选择， 显然1 不需要选， 而同时 3*3 > 2*2*2. 所以尽量拆分成3 就会得到最大乘积。
