动态规划与最大递增序列

282842712474

已知$n$个有限整数集，标号为$s_1, ..., s_n$，分别从$s_1,...,s_n$中各选取1个数字，组成序列$a_1,...,a_n$，要使得$a_1,...,a_n$拥有最长的递增子序列（这里的子列要求相邻，即$a_1,...,a_n$中存在子列$a_{n_0} < a_{n_0+1} < ... < a_{n_0+k}$且$k$最大）。

求编程实现思路～


背景

“2012年01月”假设是个实体，然后我说“2012年1月”，也要匹配上“2012年01月”

为了效率，我就把“2012年1月”逐字匹配，得到的结果是：第一个数字2，匹配了“2012年01月”的第1、4个位置，第二个数字0，匹配了第2个位置，以此类推，我得到
[1,4]
[2]
[3,7]
…
理论上所有序列都有可能，我要找出最大的递增的序列，来看它与“2012年01月”有多匹配。这个例子应该要找到[1,2,3,4,5,7,8]。

要考虑递增，是因为一般情况下来说，文本允许增删，也允许错别字，但不允许乱序。