trovare il sottoinsieme crescente maggiore di un array (non contiguo)
Domanda
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.
Soluzione
Wikipedia ha uno pseudo-codice per un algoritmo efficiente:
http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow