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

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