finding largest increasing subset of an array (non-contiguous)

Question

How can I find the largest increasing (non-contiguous) subset of an array? For example, if A= array(50,1,4,9,2,18,6,3,7,10) the largest increasing non-contiguous subset is either (1,4,6,7,10) or (1,2,6,7,10). I can intuitively see how to find the subset, but I don't know how to design the algorithm. thanks.

Answer 1

Wikipedia has pseudo-code for an efficient algorithm:

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

Answer 2

Also see Programming Pearls for more homework clues and programming tips.