343. 整数拆分

题目描述

给定一个正整数 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;
    }