encontrar el mayor subconjunto cada vez mayor de una matriz (no contiguo)

Question

¿Cómo puedo encontrar el mayor subconjunto creciente (no contiguo) de una matriz? Por ejemplo, si A = matriz (50,1,4,9,2,18,6,3,7,10), el mayor subconjunto no contiguo creciente es (1,4,6,7,10) o ( 1,2,6,7,10). Puedo ver intuitivamente cómo encontrar el subconjunto, pero no sé cómo diseñar el algoritmo.

Answer 1

Wikipedia tiene pseudo-código para un algoritmo eficiente:

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