贪心思想+快速幂求余

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例1

• 输入: 2

• 输出: 1

• 解释: 2 = 1 + 1, 1 × 1 = 1

示例2

• 输入: 10

• 输出: 36

• 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示

• 2 <= n <= 1000

方法：快速幂求余

设一绳子长度为 n ( n>1 )，则其必可被切分为两段 n=n1 +n2。

根据经验推测，切分的两数字乘积往往比原数字更大，即往往有 n1 × n2 >n1 +n2 =n 。

• 例如绳子长度为 6 ： 6=3+3<3×3=9 ；

• 也有少数反例，例如 2 ： 2=1+1>1×1=1 。

推论一： 合理的切分方案可以带来更大的乘积

设一绳子长度为 n ( n>1)，切分为两段 n=n1 +n2，切分为三段 n=n1 +n2 +n3。

根据经验推测，三段 的乘积往往更大，即往往有 n1n2n3 >n1n2。

• 例如绳子长度为 9 ： 两段 9=4+5 和 三段 9=3+3+3，则有 4×5<3×3×3 。

• 也有少数反例，例如 6 ： 两段 6=3+3 和 三段 6=2+2+2，则有 3×3>2×2×2 。

推论二： 若切分方案合理，绳子段切分的越多，乘积越大

总体上看，貌似长绳子切分为越多段乘积越大，但其实到某个长度分界点后，乘积到达最大值，就不应再切分了。

问题转化： 是否有优先级最高的长度 x 存在？若有，则应该尽可能把绳子以 x 长度切为多段，以获取最大乘积。

推论三： 为使乘积最大，只有长度为 2 和 3 的绳子不应再切分，且 3 比 2 更优

详情见下表

代码如下：

复杂度分析

• 时间复杂度 ： O(log 以2为底 N 的对数) ,其中 N=a ，二分法为对数级别复杂度，每轮仅有求整、求余、次方运算。

• 求整和求余运算：不超过机器数的整数可以看作是 O(1)；

• 幂运算：提到浮点取幂为 O(1) 。

• 空间复杂度 ： O(1) ，变量 i, b, p, rem 使用常数大小的额外空间。

END

本文内容出处是力扣官网，希望和大家一起刷算法，在后面的路上不变秃但是变强！

好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。