求数组中最长递增子序列

今天睡前翻看《编程之美》，这是每晚的必读。程序与数学在这帮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必然不可能成为整个程序的最终结果。

[原创]搜索引擎分词算法

最近在写www.bitok.cn的时候,一直在想方设法的优化搜索引擎的人工智能程度. 主要在中文分词上,自动分析用户的想法.

1 .比如有朋友搜索 "北京 大学". 那么SE(以后简称代替搜索引擎) 会根据 空格 把 关键字 分成 "北京"和"大学".

2. 但是如果把 空格去掉,输入 "北京大学". 那么就是一个不同的结果,精确搜索结果.

但如果要保证最大模糊度+最高精确度,这个就是难度了.

举个例子,我输入"北京大学", 我希望把 直接匹配的 "北京大学"(参见2的搜索结果) 排在前面,同时兼顾"北京" "大学"的分词,把相应模糊结果跟着搜索出来. 这个就是难点了.

参考了google算法之美. 我发现了一些方法. 比如某个关键词 "发展中国家" .

他主要的分词归类是 1."发展中"+"国家", 2. "发展"+"中国"+"家"

最普遍的方法是,根据词库,把1,2 的组合 带入到 词库(这里我们先忽略词库本身的不确定因素)中,去判断1和2所出现的概率, 最高的为最优.

-----------

但是最近闲看空气动力学的计算力学分析,其方法就是把力学问题的数学模型进行尽可能小粒度的微分,然后分析后综合.


所以我想到一个方法,就是把关键词(比如 "发展中国家" )全部按 字 来分开,比如 "发"+"展"+"中"+"国"+"家",

代入到搜索SE中用搜索,结果为 QuerySet0.

然后重新组成序列:
------------ "发展"+"展中"+"中国"+"国家"+"发展中"+"展中国"+"中国家"+"发展中国"+"展中国家".

然后带入到词库中. 假设词库足够的常用词汇统计,那么他就会把序列缩减为:
------------ "发展"+"中国"+"国家"+"发展中".

这时候再对QuerySet0分别对以上4个词进行查询,得出Query1,Query2,Query3,Query4.(每个集合中肯定有结果是重复的)

然后把Query1~4 进行整合.统计出每个结果被重复的次数.其中重复次率最高的分词结果则是最优分词结果.

(完)