题目描述[原题描述][https://www.acwing.com/problem/content/description/24/]
给你一根长度为 n
绳子,请把绳子剪成 m
段(m
、n
都是整数,2≤n≤58
并且 m≥2
)。
每段的绳子的长度记为k[0]、k[1]、……、k[m]。 可能的最大乘积是多少?
例如当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到最大的乘积18。
样例
1 | 输入:8 |
算法描述
大佬题解(YXC)
首先把一个正整数 N拆分成若干正整数只有有限种拆法,所以存在最大乘积。
假设 N=n1+n2+…+nk
,并且 n1×n2×…×nk
是最大乘积。
- 显然1不会出现在其中;
- 如果对于某个
i
有ni≥5
,那么把ni
拆分成3+(ni−3)
,我们有3(ni−3)=3ni−9>ni
; - 如果
ni=4
,拆成 2+2乘积不变,所以不妨假设没有4; - 如果有三个以上的2,那么 3×3>2×2×2,所以替换成3乘积更大;
综上,选用尽量多的3,直到剩下2或者4时,用2。
时间复杂度分析:当 n比较大时,n会被拆分成⌈n/3⌉
个数,我们需要计算这么多次减法和乘法,所以时间复杂度是 O(n)。
C++代码
1 | class Solution { |
Java代码
1 | class Solution { |