【力扣】343. 整数拆分

【力扣】343. 整数拆分

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

示例 1:

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

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

答案：

class Solution {
    public int integerBreak(int n) {
        //任何大于1的数都可由2和3相加组成（根据奇偶证明）
        // 因为2*2=1*4，2*3>1*5, 所以将数字拆成2和3，能得到的积最大
        // 因为2*2*2<3*3, 所以3越多积越大 时间复杂度O(n/3)，用幂函数可以达到O(log(n/3)), 因为n不大，所以提升意义不大，我就没用。 空间复杂度常数复杂度O(1)
        if(n == 1 || n == 2) return 1;
        if(n == 3) return 2;
        int count = 1;
        while(n > 4){
            count *= 3;
            n -= 3;
        }
        return count * n;
    }
}