一道快手的算法面试题没想到对数学要求还蛮高的！

　　今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题14.I 剪绳子。根据统计，近期出现在快手的算法面试环节，属于中等难度，需要一定的数学功底。

　　给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n1并且m1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

　　设绳子长度为，总共拆分为段，每一段的长度均为，请问 每一段的长度为多少时，乘积最大呢？

　　设绳子的长度为，且切分为段，则得到的乘积为（这里我们假设每一段的长度均为，则这道题目就转化为一个求函数关于的一个最大值问题，稍微翻一下大学课本里的高等数学书中求导相关的内容，接着看；

　　即，当每一段绳子的长度取时，乘积取得最大值，但是每一段绳子的长度只能取整数，到底是取 2 好 还是取 3 好呢？

　　当时，等分的话，可以是，也可以是，乘积则分别对应和，显然，所以当然是取 3 好了。

　　也就是说对于长度为的绳子，我们尽可能以每一段为 3 进行分割，得到的乘积最大。

　　当绳子的长度时，我们就可以直接用对 3 进行求余运算，设商数为，余数为，即，其中余数又分为三种情况进行处理：

　　余数，此时直接返回即为最大的乘积，比如是，最大乘积为；时，最大乘积为；整除的情况都是如此。

　　因为对于的绳子而言，我们完全可以拆分得到长度为 3、2 和 1 的绳子，拆分得到长度为 3 的绳子不必再拆分，算入乘积的线 同理。在举个栗子，比如，我们可以拆分为、和，而 3 、2 和 1 都是最终直接作为计算乘积时的因子出现的，所以.

　　对于长度为的绳子而言，要取得最大乘积，就需要知道它的前 3 个状态、和，而相应的最大乘积分别为：、和，的最大乘积则取三者中的最大值。

　　按照贪心策略来剪绳子，当时，我们尽可能多地剪长度为 3 的绳子；当剩下的绳子长度为 4 时，把绳子剪成长度为 2 的两段绳子，因。

　　接下来我们将会在该公众号上，为大家分享优质的算法解题思路，坚持每天一篇原创文章的输出，如果没有更新，说明我还在制作动画中^_^返回搜狐，查看更多

作者：admin

抖音快手 站点 QQ交谈