größte zunehmende Teilmenge eines Arrays zu finden (non-contiguous)

Question

Wie finde ich die größte Steigerung (nicht zusammenhängende) Teilmenge eines Arrays? Wenn beispielsweise A = array (50,1,4,9,2,18,6,3,7,10) die größte Erhöhung nicht zusammenhängende Teilmenge entweder (1,4,6,7,10) oder ( 1,2,6,7,10). Ich kann intuitiv sehen, wie die Teilmenge zu finden, aber ich weiß nicht, wie der Algorithmus zu entwerfen.

Answer 1

Wikipedia hat Pseudo-Code für einen effizienten Algorithmus:

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