整数拆分

题目描述

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

示例 1:

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

示例 2:

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

说明: 你可以假设 n 不小于 2 且不大于 58。

解法

本题利用贪心法求解。

当 n>=5 时，尽可能多地拆分为 3。当剩下的正数为 4 时，把正数拆分为两个 2。

证明：

首先，当 n>=5 时，可以证明 2(n-2)>n，并且 3(n-3)>n。也就是说，数字大于等于 5 时，把它拆分为数字 3 或者 2。

另外，当 n>=5 时，3(n-3)>=2(n-2)。因此，尽可能多地拆分为整数 3。

当 n=4 时，其实没必要拆分，只是题目要求至少要拆分为两个整数。那么就拆分为两个 2。

class Solution {
    public int integerBreak(int n) {
        if (n < 2) {
            return 0;
        }
        if (n < 4) {
            return n - 1;
        }
        
        int timesOf3 = n / 3;
        if (n % 3 == 1) {
            --timesOf3;
        }
        int timesOf2 = (n - timesOf3 * 3) >> 1;
        return (int) (Math.pow(2, timesOf2) * Math.pow(3, timesOf3));
    }
}