据说这是一道快手的面试题。

描述：

原意：

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段(m、n都是整数，n>1并且m>1)，

每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问  可能的最大乘积是多少？

例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

人话：

拆解一个数，使其乘积最大

思路：

这是个数学问题。

如果你明白了这是个数学问题，你会发现这其实是道简单题目。

要拆解一个数，而且子集的和要原数一致，得到最大的乘积。

假如一个数小于等于 3，乘积应该是 n-1

假如一个数 4，乘积最大应该 是 2*2=4

假如一个数 5，乘积最大应该 是 3*2=6

假如一个数 6，乘积最大应该 是 3*3=9

假如一个数 7，乘积最大应该 是 3*2*2=12

规律：

倒序看一下，一个数拆解成3或者2，才会有最大的乘积。

如果最后剩下的差是 4，那么应该拆成 2*2，而不是 3*1

所以，这是一道贪心算法。

public class 快手剪绳子 {
    public static void main(String[] args) {
        System.out.println(cuttingRope(4));
        System.out.println(cuttingRope(6));
        System.out.println(cuttingRope(8));
        System.out.println(cuttingRope(9));
        System.out.println(cuttingRope(10));
        System.out.println(cuttingRope(11));
    }
    /**
     * 贪心算法   O(1)
     *
     * 当取 3 时，有最大乘积，否则取2。
     * 如果最后是4，那么应该拆成 2*2，而不是 3*1
     *
     * @param n
     * @return
     */
    public int cuttingRope3(int n) {
        if (n <= 3) {
            return n - 1;
        }
        //有多少个3
        int NumOf3 = n / 3;
        //判断最后是否是 4
        if (n - NumOf3 * 3 == 1) {
            //如果是4，应该拆成 2*2
            NumOf3--;
        }
        //有多少个2
        int NumOf2 = (n - NumOf3 * 3) / 2;
        return (int) Math.pow(3, NumOf3) * (int) Math.pow(2, NumOf2);
    }
}