trovare il sottoinsieme crescente maggiore di un array (non contiguo)

Question

Come posso trovare il sottoinsieme crescente (non contiguo) più grande di un array? Ad esempio, se A = array (50,1,4,9,2,18,6,3,7,10) il sottoinsieme non contiguo crescente maggiore è (1,4,6,7,10) o ( 1,2,6,7,10). Posso intuitivamente vedere come trovare il sottoinsieme, ma non so come progettare l'algoritmo.

Answer 1

Wikipedia ha uno pseudo-codice per un algoritmo efficiente:

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