题目主要信息

1、给出一根长度为n的绳子

2、将绳子截成m段，m>2，使得所有乘积最大

方法一:贪心算法

具体方法

本题是JZ14的进阶版，主要的区别在于绳子的长度在JZ14中为小于60，二在本题中为10的14次方，因此JZ14中的动态规划方法在本题中无法使用。

首先，我们可以把这题转化成一道数学问题，把绳子切割成若干份，使得其乘积最大，首先通过算术几何均值不等式可得

因此，需要把绳子切成尽量相等的若干份，接下来问题就是在于每一段的长度。 设将绳子按照相等长度等分为若干段，即n = a * x，那么目标函数即为最大化$x^{\frac{n}{x}}x^\backslash frac\{n\}\{x\}$，其中n为常数，经过求导，可以得到x为3时，结果最大。因此，我们的划分方式如下图

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number long长整型 
     * @return long长整型
     */
    public long cutRope (long number) {
        // write code here
        if(number<=3){
            return number-1;
        }
        long ans = 1;
        while(number>4){
            ans = (ans*3)% 998244353;
            number -= 3;
        }
        return number*ans % 998244353;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，循环次数为n/3
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：快速幂

具体方法

虽然方法一时间复杂度为$O(n)O(n)$，但是由于绳子长度较长，在循环迭代过程中出现了超时情况，因此需要考虑进行优化。由于主要的计算时间在求取幂的部分，因此主要优化方向就是通过快速幂的方法来减少时间复杂度。

快速幂的公式如下图所示：

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number long长整型 
     * @return long长整型
     */
    long mod = 998244353;
    public long cutRope (long number) {
        if(number<=3) return number-1;
        long a = number/3;
        long b = number%3;
        if(b==0) return Pow(3, a) % mod;
        else if(b==1) return Pow(3, a-1) * 4 % mod;
        else return Pow(3, a) * 2 % mod;
    }
    public long Pow(long base, long num){
        long res = 1;
        while(num > 0){
            if(num%2==1){
                res = res * base % mod;
            }
            base = base * base % mod;
            num >>= 1;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：$O(logn)O(logn)$，循环次数为$lognlogn$
• 空间复杂度：$O(1)O(1)$，无额外空间