Problem 343: Integer Break

https://leetcode.com/problems/integer-break/

思路

https://discuss.leetcode.com/topic/45341/a-simple-explanation-of-the-math-part-and-a-o-n-solution

这就是一个数学题，其实没啥意思

• 如果想要使最后的 product 最大，那么就要让被分解的这些数字尽可能相等！

• 对于不同的 factor，当 n 是偶数时， $(n/2)*(n/2)$ 最大；当 n 是奇数的时候，$(n - 1)/2 * (n + 1) / 2$ 最大。

• 当 $n >= 4$ 的时候, $(n/2)*(n/2)>=n$； 当 $n>=5$ 的时候，$(n-1)/2 *(n+1)/2>=n$，也就是说，备选的 factor 只可能是 1, 2，3， 而这三个数，越大的最后乘积越大。所以我们尽可能多选 3。

public class Solution {
    public int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;

        int product = 1;
        while (n > 4) {
            product *= 3;
            n -= 3;
        }
        product *= n;

        return product;
    }
}