IntegerBreak.java

package com.company;

public class IntegerBreak {
    /**
     * 这道题给了我们一个正整数n，让我们拆分成至少两个正整数之和，使其乘积最大，题目提示中让我们用O(n)来解题，而且告诉我们找7到10之间的规律，那么我们一点一点的来分析：
     * <p>
     * 正整数从1开始，但是1不能拆分成两个正整数之和，所以不能当输出。
     * <p>
     * 那么2只能拆成1+1，所以乘积也为1。
     * <p>
     * 数字3可以拆分成2+1或1+1+1，显然第一种拆分方法乘积大为2。
     * <p>
     * 数字4拆成2+2，乘积最大，为4。
     * <p>
     * 数字5拆成3+2，乘积最大，为6。
     * <p>
     * 数字6拆成3+3，乘积最大，为9。
     * <p>
     * 数字7拆为3+4，乘积最大，为12。
     * <p>
     * 数字8拆为3+3+2，乘积最大，为18。
     * <p>
     * 数字9拆为3+3+3，乘积最大，为27。
     * <p>
     * 数字10拆为3+3+4，乘积最大，为36。
     * <p>
     * ....
     * <p>
     * 那么通过观察上面的规律，我们可以看出从5开始，
     * 数字都需要先拆出所有的 3，一直拆到剩下一个数为 2 或者 4，
     * 因为剩 4 就不用再拆了，拆成两个 2 和不拆没有意义，
     * 而且 4 不能拆出一个 3 剩一个 1，这样会比拆成 2 + 2 的乘积小。
     * 那么这样我们就可以写代码了，先预处理 n 为 2 和 3 的情况，
     * 然后先将结果res初始化为 1，然后当 n 大于 4 开始循环，
     * 我们结果自乘 3，n 自减 3，根据之前的分析，
     * 当跳出循环时，n只能是 2 或者 4，再乘以res返回即可：
     */
    public int integerBreak(int n) {
        if (n == 2 || n == 3) return n - 1;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }
}