最长下降/上升子序列的问题,复杂度到底是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叉树来存储并排序，得到的不过是一个整体的排序结果，不是要求的最长子序列的长度啊。
