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.
Solution
Wikipedia has pseudo-code for an efficient algorithm:
http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow