1. 题目描述
给你一根长度为n的绳子，请把绳子剪成整数长度的m段（m、n都是整数，n > 1并且m > 1），每段绳子的长度记为k[0],k[1]...k[m-1]。请问k[0]*k[1]*...*k[m-1]可能的最大乘积是多少？例如，当绳子的长度是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
来源：力扣（LeetCode）
2. 解题思路
给定一个数，假设将其拆分成个因子。根据均值不等式，当且仅当时，有最大。
考虑函数 求导得 因此，当时，单减。时，取得最大值。
所以，我们的划分因子数应当为： 以上的讨论虽然找出了极值点，但局限于连续的情形下。题目的要求是分割为整数段，我们只能求出函数的极值点，然后分别尝试极值点左右的值。
比如，当时，计算出的极值点。我们自然会依次尝试它的左右整数点和，并尽可能将均分。但可惜的是，无论取和，都不是本题的最优解。例如，当时，我们将拆分为，乘积为。然而，注意到时，乘积为，为最大值。
出现这个现象的原因是，时正好将均分了，根据均值不等式，可以取得最大值，而时并不能均分，求得的值要比最大值小一些。因此，我们只得扩大我们的尝试范围，左右再多尝试一个值。
根据此方案，得到的算法如下。
class Solution {
public:
int cuttingRope(int n) {
float e = 2.71828;
int left = floor(n / e), right = ceil(n / e);
if (left <= 1)
return left == 0 ? 1 : 2 * (n - 2);
int pt_1 = calc(n, left - 1), pt_2 = calc(n, left);
int pt_3 = calc(n, right), pt_4 = calc(n, right + 1);
return max(max(pt_1, pt_2), max(pt_3, pt_4));
}
int calc(int n, int k) {
int factor = n / k, prod = 1;
for (int i = 0, j = 0; i < k; i++, j++)
prod *= j < n - factor * k ? factor + 1 : factor;
return prod;
}
};
|
上述算法虽然已经可以解决问题，但可以进一步优化。我们从数学上计算了极值点为 这告诉我们，只要每次尽量从绳子中分出长度的段，就越能逼近最大值。由此，我们可以得出改进算法的思路，每次从绳中分出长度为的段，但要注意，当时，分出一段长度为的绳子才能使乘积达到最大。
class Solution {
public int cuttingRope(int n) {
if (n <= 4)
return n <= 2 ? 1 : n == 3 ? 2 : 4;
int prod = 1;
while (n > 4) {
prod *= 3; n -= 3;
}
return prod *= n;
}
}
|
算法复杂度
