题目描述
给你一根长度为 nn 绳子,请把绳子剪成 mm 段(mm、nn 都是整数,2≤n≤582≤n≤58 并且 m≥2m≥2)。
每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少?
例如当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到最大的乘积18。
样例
输入: 12
输出:81
算法讲解
在输入12时, 显然3x3x3x3的结果,要比4x4x4的结果要大
1. 一定不能出现为1的段
2.能用3凑绝不用2
3.无法用3再考虑2
时间复杂度 $O(n)$
python 代码
class Solution(object):
def maxProductAfterCutting(self,length):
"""
:type length: int
:rtype: int
"""
num = length // 3
remainder = length % 3
if length < 2:
return None
elif length == 2:
area = 1
else:
if remainder == 0:
area = pow(3, num)
elif remainder == 1:
num = num - 1
area = pow(3, num) * 2 * 2
else:
area = pow(3, num) * 2
return area