343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

 

思路:

  根据贪心算法，就尽量将原数拆成更多的 3

 

如果整数 n 的形式是 3k+1，例如 7。按照上面规则，会拆分成“3 + 3 + 1”。 1 是没作用的。此时，应该将 1 和 3 变成 4，也就是“3 + 3 + 1”变成“3 + 4”。此时乘积最大

   

综上所述，算法的整体思路是：

n 除 3 的结果为 a，余数是 b
当 b 为 0，直接将 a 个 3 相乘
当 b 为 1，将（a-1）个 3 相乘，再乘以 4
当 b 为 2，将 a 个 3 相乘，再乘以 2​​​​​​​ 

class Solution {
    public int integerBreak(int n) {
        /**
        一直 n 不小于 2 且不大于 58。
        贪心: 尽量拆多个3 
            如果余数是1 ,就(n-1)个三,1个四

            n 除 3 的结果为 a，余数是 b
                当 b 为 0，直接将 a 个 3 相乘
                当 b 为 1，将（a-1）个 3 相乘，再乘以 4
                当 b 为 2，将 a 个 3 相乘，再乘以 2 
         */
        if(n==2){
            return 1;
        }
        if(n==3){
            return 2;
        }
       
         int a=n/3;
         int b=n%3;
         if(b==0){
               return (int)( Math.pow(3,a));
         }
         else if(b==1){
             return (int)(4*Math.pow(3,a-1));
         }

         return (int)(b*Math.pow(3,a));
    }
}