一道快手的算法面试题没想到对数学要求还蛮高的！ - 五分钟学算法的个人空间 - OSCHINA

　　今天分享的题目来源于 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 data-formula-type=inline-equation style=>

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

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

　　因为对于3 data-formula-type=inline-equation style=>

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

　　对于长度为3 data-formula-type=inline-equation style=>

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

作者：admin

抖音快手 站点 QQ交谈