c语言背包问题_背包问题 贪心算法_c语言背包问题csdn(3)

扩展：

求解lis的加速

难度评级：★★

分析：

在构造lis[k+1]的时候可以发现，对于s[k+1]，真正有用的元素s[i]<s[k+1]且lis[i]最大。如果记录了不同长度的lis的末尾元素，那么对于新加入的元素s[k+1]，找出前面比它小的且对应lis最长的，就是以s[k+1]为结尾的lis[k+1]的长度。

可以发现使用数组MaxV[1...MAXLENGTH]其中MaxV[i]表示长度为i的lis的最小末尾元素，完全可以在s[k+1]时进行lis[k+1]的更新。进一步地发现，其实lis[]数组已经没有用了，对于MaxV[1...MAXLENGTH]中值合法对应的最大下标，就是当前最长的lis，也即利用MaxV[]更新自身。

同时，根据MaxV[]的更新过程，可以得出当i<j时，MaxV[i]<MaxV[j]（假设出现了i>j且Max[i]=>Max[j]的情况，那么在之前的处理中，在发现j长度的lis时，应用它的第i个元素来更新Max[i]，仍会导致MaxV[i]<MaxV[j]，这与这个现状发生了矛盾，也即这个情况是不可能到达的）。这样，在寻于s[k+1]的值时，可以使用二分查找，从而把时间复杂度降低至O(nlogn)。

在这个解法下，不妨考虑如何重构这个lis。

难度评级：★

输入是具有n个数的向量x，输出时输入向量的任何连续子向量的最大和。

解法：

求和比较简单，以前写过比较全面的分析：

这里只把O(n)的动态规划解法列在下面，其中只用一个变量保存过去的状态：

扩展1：

难度评级：★

给定一个正浮点数数组，求它的一个最大连续子序列乘积的值。

解法：

对数组中每个元素取对数，构成新的数列，在新的数列上使用求最大连续子序列的算法。

如果求对数开销较大，建议使用扩展2的方法。

扩展2：

难度评级：★

给定一个浮点数数组，其值可正可负可零，求它的一个最大连续子序列乘积的值。（假定计算过程中，任意一个序列的积都不超过浮点数最大表示）

解法：

在最大连续子序列和算法的基础上进行修改。由于负负得正，对于当前状态array[k]，需要同时计算出它的最大值和最小值。即：

new_maxendinghere = max3(maxendinghere*array[k],minendinghere*array[k],array[k])

new_minendinghere = min3(maxendinghere*array[k],minendinghere*array[k],array[k])

此后对已遍历部分的最大积进行更新：

maxsofar = max(maxsofar,new_maxendinghere)

如果不习惯用常数个变量来表示，可以看看，再想想用数组保存是不是浪费了空间。（计算max[k]、min[k]只用到了max[k-1]、min[k-1]，没有必要保存全部状态）

难度评级：★

一个给定的矩阵序列A1A2...An计算连乘乘积，有不同的结合方法，并且在结合时，矩阵的相对位置不能改变，只能相邻结合。根据矩阵乘法的公式，10*100和100*5的矩阵相乘需要做10*100*5次标量乘法。那么对于维数分别为10*100、100*5、5*50的矩阵A、B、C，用(A*B)*C来计算需要10*100*5 + 10*5*500 =7500次标量乘法；而A*(B*C)则需要100*5*50+10*100*50=75000次标量乘法。

那么对于由n个矩阵构成的链<A1,A2,...,An>，对i-1,2,...n，矩阵Ai的维数为pi-1*pi，对乘积A1A2...An求出最小化标量乘法的加括号方案。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-23984-3.html