求数组中最长递增子序列

今天睡前翻看《编程之美》，这是每晚的必读。程序与数学在这帮Microsoft的天才工程师们手中结合得通俗易懂。
当中有个题目：写一个时间复杂度尽可能低的程序，求数组最长递增子序列 的解答方式让我觉得是那么不尽人意。
原题：求一个1维数组（N个元素）中的最长递增子序列的长度。
例如 L = [1,-1,2,-3,4,-5,6,-7] 的最长子序列是 1,2,4,5.

书上的解答思路过于注重了各个元素之间相互的比较。从系统工程学来解释就是内耗过大。所以在这样的思路下，书上的最低时间复杂度为O(n*logn).

于是我干脆跳出了这样一个思路。把时间复杂度控制到了O(n).

1 取出第1个元素E1为新的序列S1,
2 取出第2个元素E2和E1做比较，如果E2>E1，则追加到S1中; 否则，把E2放到新序列S2中
3 取出第3个元素E3和所有已有序列的最后一个元素比较，判断法则如同步骤2
.......
当序列遍历完成时，程序结束。

这是一个动态规划的思想。 就拿L为例,遍历L：每个虚线之间代表一个步骤
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1
－1
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1，2
－1，2
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1，2
－1，2
－3
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1，2，4
－1，2，4
－3，4
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1，2，4
－1，2，4
－3，4
－5
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1，2，4，6
－1，2，4，6
－3，4，6
－5 ，6
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1，2，4，6
－1，2，4，6
－3，4，6
－5 ，6
－7
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－


遍历结束。这样就列举出了所有的递增子序列，自然最长序列一目了然。但是这样的空间消耗又大了。 那么我们可以在这个基础上优化空间。
我们观察上面的各个步骤可以发现：
如果各个序列组的最后一个元素相同，那么非最长序列就一定不可能是后结果。（相关证明请参见文章末尾）
这样的话，我们重新遍历L。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1
－1
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1，2
－1，2
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1，2
－1，2
－3
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1，2，4
－1，2，4
－3，4 该序列可删除
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1，2，4
－1，2，4
－5
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1，2，4，6
－1，2，4，6
－3，4，6 该序列可删除
－5 ，6 该序列可删除
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1，2，4，6
－1，2，4，6
－5 ，6
－7
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
（完）


证明： 如果各个序列组的最后一个元素相同，那么非最长序列就一定不可能是后结果。
blogspot不支持TeX公式所以这里用文字叙述。

对于S1,S2....SN满足S1.LastElement = .... = SN.LastElement
=> 当L中取出元素E作比较，
如果E>S1.LastElement,则E>Sx.LastElement， 其中x属于1......N.
如果E无论L中的元素为何值，则S1到SN之间的长度大小关系不变。
=>S1到SN中的最长序列Smax不变（注意不是长度不变，而是序号不变）。
=>如果Sx不是最长序列，则Sx必然不可能成为整个程序的最终结果。