поиск наибольшего возрастающего подмножества массива (несмежного)

Question

Как найти наибольшее увеличивающееся (несмежное) подмножество массива?Например, если A= array(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