encontrando maior subconjunto crescente de uma matriz (não contígua)

Question

Como posso encontrar o maior aumento subconjunto (não contíguas) de uma matriz? Por exemplo, se A = matriz (50,1,4,9,2,18,6,3,7,10) o maior aumento subconjunto não-contíguo é ou (1,4,6,7,10) ou ( 1,2,6,7,10). Posso intuitivamente ver como encontrar o subconjunto, mas eu não sei como projetar o algoritmo.

Answer 1

Wikipedia tem pseudo-código para um algoritmo eficiente:

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