最长下降/上升子序列的问题,复杂度到底是O(n^2)还是O(nlgM)呢?
看了几篇动态规划的入门教程，求最长下降/上升子序列的问题都是给出了O(n^2)的算法复杂度。
可是看网上又有很多人说nlgM(M是子序列长度)就可以了，一种说法是这样描述的:
------------------------------------
"我想到的是一个N*logn(M)(M为最终不下降序列的长度)复杂度的解法！
首相遍历一下这个数组，之后记录一个不下降序列的数组A，遇到一个数字a，就在中查找大于a的数据，如果没有就向A中添加a，这里的复杂度就是（Log（M))，这样循环走一遍序列就可以得到一个不下降序列了，A的长度就是解了"
------------------------------------
问题是，我觉得N*logn(M)的这个所谓的解法，用伪代码根本描述不出来。假设我们用数组来存储N个数据，用一颗排序2叉树来存储并排序，得到的不过是一个整体的排序结果，不是要求的最长子序列的长度啊。
[解决办法]
参见：http://topic.csdn.net/u/20100424/22/7a7b4a50-9110-4cf8-96ec-7fa728593b15.html
[解决办法]
由于数组A有序,且为升序,因此采用二分查找,查找操作的时间复杂度为O(lgn),其中n为数组A的长度,因此总的时间复杂度为O(nlgn),其中n为序列长度.并不是O(nlgm),因为这是上界表示,而m最大可达到n.
这个方法其实就是利用二分法优化这个1D/1D状态转移方程.
定义d[i]为i之前能构成的最长不降子序列的长度,d[i]=max(d[j]+1),1<=j<i && number[j]<number[i].
答案为max(d[i]),1<=i<=n,其中n为序列长度.
如何优化?考虑两个状态d[a],d[b],以及a,b处的数字number[a],number[b],且number[a]<number[b],如果存在一个i,使number[i]>=number[b],那么number[i]一定大于number[a],如果此时有d[a]>d[b],那么我们选则a转移得到的长度一定不会比在b转移差,b就可以丢掉啦,根据这个原理........各种优化方法啦啦啦>_<
