給你一根長度為 n 的繩子，請把繩子剪成整數(shù)長度的 m 段（m、n都是整數(shù)，n>1并且m>1），每段繩子的長度記為 k[0],k[1]...k[m-1] 。請問 k[0]*k[1]*...*k[m-1] 可能的最大乘積是多少？例如，當(dāng)繩子的長度是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

方法：貪心思路

設(shè)一繩子長度為 n ( n>1 )，則其必可被切分為兩段 n=n1 +n2。

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

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

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

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

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

根據(jù)經(jīng)驗(yàn)推測，三段 的乘積往往更大，即往往有 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。

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

總體上看，貌似長繩子切分為越多段乘積越大，但其實(shí)到某個長度分界點(diǎn)后，乘積到達(dá)最大值，就不應(yīng)再切分了。

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

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

詳情見下表。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度 ： O(1)，僅有求整、求余、次方運(yùn)算。

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

• 冪運(yùn)算：提到浮點(diǎn)取冪為 O(1) 。

• 空間復(fù)雜度 ： O(1) ，變量 a 和 b 使用常數(shù)大小的額外空間。

END

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號“javaAnswer”，全部都是干貨。