מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/תת-סידרה עולה ארוכה ביותר/שאלה

הגדרה: נתונה סידרה $\displaystyle X=[x_{1}...x_{n}]$ של מספרים שונים זה מזה. $\displaystyle Y=[y_{1}...y_{m}]$ היא תת-סידרה עולה של $\displaystyle X$ אם: קיימת סדרה עולה ממש של אינדקסים $\displaystyle [i_{1},...,i_{m}]$ כך ש$\displaystyle x_{i_{j}}=y_{j}$ לכל $\displaystyle j$. $\displaystyle Y$ היא סידרה עולה.

דוגמה: נניח ש$\displaystyle X=[1,5,2,3]$. אם נקבע $\displaystyle Z=[1,2,3]$, אז $\displaystyle Z$ היא תת-סידרה עולה של $\displaystyle X$. גם אם נקבע $\displaystyle Z=[2,3]$ תהיה $\displaystyle Z$ תת-סידרה עולה של $\displaystyle X$.

הגדרה: אם $\displaystyle X$ היא סידרה, אז $\displaystyle Y$ היא הLIS (או longest increasing subsequence), אם היא הארוכה ביותר מבין תתי-הסדרות העולות של $\displaystyle X$.

הנח שX הוא מערך גלובלי המתאר את הסדרה $\displaystyle X$, בעלת האורך $\displaystyle n$. בשאלה זו עליך למצוא אלגוריתם יעיל למציאת אורך הLIS.