给你一根长度为 n n n 绳子,请把绳子剪成 m m m 段( m m m、 n n n 都是整数, 2 ≤ n ≤ 58 2≤n≤58 2≤n≤58 并且 m ≥ 2 m≥2 m≥2)。
每段的绳子的长度记为 k [ 1 ] 、 k [ 2 ] 、 … … 、 k [ m ] k[1]、k[2]、……、k[m] k[1]、k[2]、……、k[m]。
k [ 1 ] , k [ 2 ] , … , k [ m ] k[1],k[2],…,k[m] k[1],k[2],…,k[m] 可能的最大乘积是多少?
例如当绳子的长度是 8 8 8 时,我们把它剪成长度分别为 2 2 2、 3 3 3、 3 3 3 的三段,此时得到最大的乘积 18 18 18。
样例
输入:8 输出:18
- 1
- 2
- 3
首先把一个正整数 N N N 拆分成若干正整数只有有限种拆法,所以存在最大乘积。
假设 N = n 1 + n 2 + … + n k N = n_1+n_2+…+n_k N=n1+n2+…+nk ,并且 n 1 × n 2 × … × n k n_1×n_2×…×n_k n1×n2×…×nk 是最大乘积。
综上,尽可能的拆分到最多的 3 3 3 ,余下的 2 2 2 或 4 4 4 优先选择 2 2 2 。另外,这里需要注意 m m m 必须大于等于 2 2 2 ,所以绳子至少要分两段。
class Solution {
public:
int maxProductAfterCutting(int length) {
if (length <= 3) return length - 1;
int res = 1;
//将lenght变成3的倍数
if (length % 3 == 2) res = 2, length -= 2;
if (length % 3 == 1) res = 4, length -= 4; //两个2相乘
while (length) res *= 3, length -= 3;
return res;
}
};
欢迎大家在评论区交流~