trouver le plus grand sous-ensemble croissant d'un tableau (non contigu)

Question

Comment puis-je trouver le plus grand sous-ensemble croissant (non contigu) d'un tableau? Par exemple, si A = array (50,1,4,9,2,18,6,3,7,10), le sous-ensemble non contigu croissant croissant est soit (1,4,6,7,10), soit ( 1,2,6,7,10). Je peux voir intuitivement comment trouver le sous-ensemble, mais je ne sais pas comment concevoir l'algorithme.

Answer 1

Wikipedia a un pseudo-code pour un algorithme efficace:

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