найти наибольшее увеличивающееся подмножество массива (несмежное)

Question

Как найти наибольшее увеличивающееся (несмежное) подмножество массива? Например, если A = массив (50,1,4,9,2,18,6,3,7,10), наибольшее увеличивающееся несмежное подмножество является либо (1,4,6,7,10), либо (1,2,6,7,10). Я могу интуитивно понять, как найти подмножество, но я не знаю, как разработать алгоритм.

Answer 1

Википедии есть псевдо-код для эффективного алгоритма:

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