剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

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

示例 2:

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

提示：

• 2 <= n <= 58

1.数学推导

我们都知道一个 “算术几何均值不等式”

当 a=b的时候，取相等，也就是ab的最大值了。

该推广的公式

• 推论 将绳子 以相等的长度等分为多段 ，得到的乘积最大。
  假设分为 段，每段长为 ，则有 , 得到的最大积

求函数 的最大值，我们转为 和 的关系 ，就是

但是n是一个常数,转而求下面的最大值

补充一点，求一个已知函数的最大值，就是求导数，然后根据一阶导数为0的点就是驻点，如果驻点左右异的话，这个驻点就可能是极值点，极值点又可能是最值点。

先求驻点，就要先求导。但是求导基本公式里面是没有 这个形式的求导的 ，做个变化，两边取对数，因为对数函数是单调递增的，所以不影响原函数的单调性。

再代入,化简

取 可得到 满足表达式，通常是猜值法，但是这个只能找到一个驻点，不能说明这个驻点是唯一的。那要证明证明这个驻点唯一呢？通常的做法可以是求二阶导，但是我们这个是个有实际意义的题，且x>0。显然的正负取决于 ,1是个常数， 是单调的， 所以显然 也是单调的，那么就最多只能有一个零点，而恰好，我们猜到了是

取e左右极限，判断的正负

e左边递增加，e的右边减少，可以看出这个是个极大值点，我们前面证明了只有一个驻点，也就最多只有一个极值点，也就最多只有一个极大值点，最大值就是在所有的极大值点选。恰好只有一个，那么最大值点就是了。

如果这是个数学问题，那么就是e了，交卷。但是这是个实际意义的题，x的取值是整数。所有在e的附件取值，代入函数 比较最大值即可。

证明完毕，取3最优。

• 优先取3
• 剩下 2 ，就用2
• 剩下 1 ，拿回来一个 3 因为 $31<22$

class Solution {
    public int cuttingRope(int n) {
       if (n <= 3) {
            return n - 1;
        }

        int count = n / 3;
        int last = n % 3;
        switch (last){
            case 0:
                return (int) Math.pow(3, count);
            case 1:
                return (int) Math.pow(3, count-1)*4;
            case 2:
                return (int) Math.pow(3, count)*2;
        }
        return 0;
    }
}

执行用时 :0 ms, 在所有 Java 提交中击败了100.00% 的用户

内存消耗 :36.2 MB, 在所有 Java 提交中击败了100.00%的用户