配列の最大増加サブセットの検出（非連続）

Question

どのようにして配列の最大増加（非連続）サブセットを見つけることができますか？たとえば、A = array（50,1,4,9,2,18,6,3,7,10）の場合、増加する非連続サブセットは（1,4,6,7,10）または（ 1,2,6,7,10）。サブセットを見つける方法は直感的にわかりますが、アルゴリズムの設計方法がわかりません。

Answer 1

ウィキペディアには、効率的なアルゴリズムの擬似コードがあります：

http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem