貪心思想+快速冪求余

給你一根長度為 n 的繩子，請把繩子剪成整數(shù)長度的 m 段（m、n都是整數(shù)，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。

根據(jù)經驗推測，切分的兩數(shù)字乘積往往比原數(shù)字更大，即往往有 n1 × n2 >n1 +n2 =n 。

• 例如繩子長度為 6 ： 6=3+3<3×3=9 ；

• 也有少數(shù)反例，例如 2 ： 2=1+1>1×1=1 。

推論一： 合理的切分方案可以帶來更大的乘積

設一繩子長度為 n ( n>1)，切分為兩段 n=n1 +n2，切分為三段 n=n1 +n2 +n3。

根據(jù)經驗推測，三段 的乘積往往更大，即往往有 n1n2n3 >n1n2。

• 例如繩子長度為 9 ： 兩段 9=4+5 和 三段 9=3+3+3，則有 4×5<3×3×3 。

• 也有少數(shù)反例，例如 6 ： 兩段 6=3+3 和 三段 6=2+2+2，則有 3×3>2×2×2 。

推論二： 若切分方案合理，繩子段切分的越多，乘積越大

總體上看，貌似長繩子切分為越多段乘積越大，但其實到某個長度分界點后，乘積到達最大值，就不應再切分了。

問題轉化： 是否有優(yōu)先級最高的長度 x 存在？若有，則應該盡可能把繩子以 x 長度切為多段，以獲取最大乘積。

推論三： 為使乘積最大，只有長度為 2 和 3 的繩子不應再切分，且 3 比 2 更優(yōu)

詳情見下表

代碼如下：

復雜度分析

• 時間復雜度 ： O(log 以2為底 N 的對數(shù)) ,其中 N=a ，二分法為對數(shù)級別復雜度，每輪僅有求整、求余、次方運算。

• 求整和求余運算：不超過機器數(shù)的整數(shù)可以看作是 O(1)；

• 冪運算：提到浮點取冪為 O(1) 。

• 空間復雜度 ： O(1) ，變量 i, b, p, rem 使用常數(shù)大小的額外空間。

END

本文內容出處是力扣官網，希望和大家一起刷算法，在后面的路上不變禿但是變強！

好兄弟可以點贊并關注我的公眾號“javaAnswer”，全部都是干貨。