מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/תת-סידרה עולה ארוכה ביותר/שאלה
מראה
הגדרה: נתונה סידרה של מספרים שונים זה מזה. היא תת-סידרה עולה של אם:
|
דוגמה: נניח ש. אם נקבע , אז היא תת-סידרה עולה של . גם אם נקבע תהיה תת-סידרה עולה של . |
הגדרה: אם היא סידרה, אז היא הLIS (או longest increasing subsequence), אם היא הארוכה ביותר מבין תתי-הסדרות העולות של . |
הנח שX
הוא מערך גלובלי המתאר את הסדרה , בעלת האורך . בשאלה זו עליך למצוא אלגוריתם יעיל למציאת אורך הLIS.