题目描述给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。求解很多朋友都通过观察发现了最大解其实就是尽可能的多分长度为3的段，下面系统证明：假设得到最大乘积时，其中一段长度为k，下面通过反证法证明：k!=1且k不能再继续拆分成2和3的和证明1：先证明k!=1，假设k=1，则取其临近的一段，假设长度为l，则存在这样一种剪法：k+l为一段，其余...

看大家都是用双指针，我来写一种其他方法吧，纯数学解法假设从n开始，到n+k，连续k+1个数的和等于S,则有计算得到由n>=1得到k的范围因此只需对1->k遍历，找到满足上述公式（整除）的k，自然可以计算出对应的开始数字n，代码如下： class Solution { public: static bool compare(const vector<int>& v1, const vector<int>& v2) { return v1[0] < v2[0]; } vector<vector...

动态规划问题假设数组为则整个字符串的最大子串和为：又因为：使用自底向上的计算过程，逐次计算Sk的值，取其中的最大值，即为解 class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { if (array.empty()) { return 0; } int index = array.size() - 1; int sum = array[index]; int maxSum =...

经典问题，3种解法： 先排序，再取前k个数，平均时间复杂度O(nlogn) 使用最小堆，建堆完成后依次交换第一个和第i个元素（i=n,n-1,...,n-k）得到k个最小值，平均时间复杂度O(n+k) 使用快排的patition子程序，逐步逼近第k个数所在的位置，期望平均时间复杂度O(n)，但是前k个数并不是有序状态这题并不要求最后的结果有序，所以用第三种方法是最好的，为避免最坏情况，每次patition的基准元素随机选择这里不写具体的实现过程，因为是用C++，这里可以直接用STL提供的排序函数其中：1）若需对vector, string, deque, 或array容器进行全排序，你可选择...

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。分析：一棵二叉搜索树的后序遍历结果，必然是其中序遍历顺序入栈的其中一种出栈序列实现：先对输入进行排序获取中序遍历结果，然后使用栈模拟遍历过程，最后栈为空，则后序遍历成立，代码如下： class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { if (sequence.empty()) { return fa...