العثور على أكبر فرعية متزايد من مجموعة (غير متجاورة)

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