题目描述
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。例如：
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
解题思路
对于一个正整数n，
当n<=3时，分解结果分别为1+1，和1+2。可以将2，3看成因子分解的原子单位。
当n>3时，优先分解为3的乘积，因为3的幂大于2的幂，例如9=3+3+3和9=2+2+2+2+1。
所以另a=n/3，b=n%3。如果b=1的情况下由于有3<2*2，所以此时结果优先选取pow(3, a-1)22。
int integerBreak(int n) {
if(n<=3)
return n-1;
int a = n/3, b = n%3;
if(b==0)
return pow(3, a);
else if(b==1)
return pow(3, a-1)*4;
else
return pow(3, a)*b;
}
网友评论