摘要: 既然已经说到了最长公共子序列,就把这个递增子序列也说了。同样的,这里subsequence表明了这样的子序列不要求是连续的。比如说有子序列{1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }这样一个字符串的的最长递增子序列就是{1,3,4,5,6,7}或者{1,3,4,5,6,19}。
其实这个问题和前面的最长公共子序列问题还是有一定的关联的。假设我们的初始的序列S1。那我们从小到大先排序一下。得到了S1'。这样我们再球S1和S1'的最长公共子序列就可以知道答案了:)是不是有点巧妙啊。这个过程还是比较直观的。但是这个不是这次要说的重点,这个问题有比较传统的做法的.
我们定义L(j)是一个优化的子结构,也就是最长递增子序列.那么L(j)和L(1..j-1)的关系可以描述成
阅读全文