摘要: 既然已經說到了最長公共子序列，就把這個遞增子序列也說了。同樣的，這里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)的關系可以描述成
閱讀全文