מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/תת-סידרה עולה ארוכה ביותר/תשובה
נשתמש במספר סימונים ומשפטים פשוטים:
- נגדיר את הרישה ה של מחרוזת כ.
- נגדיר כ את אורך הLIS של שאיברה האחרון הוא .
- נשים לב ש:
- הוא אורך הLIS של .
- מקיים את הנוסחה .
בפתרון נשתמש במערך גלובלי L
המתאר, בכניסה ה, את האיבר הקטן ביותר עד כה המסיים תת-סידרה עולה באורך .
אלה שלבי פעולות הפתרון:
- נאתחל את כל אחד מאיברי
L
ל. - נעבור בלולאה, משמאל לימין, על איברי
X
. כשנגיע לאיבר ה:- נחפש את האיבר הגדול ביותר ב ב
L[1], ..., L[i - 1]
שאינו גדול מX[i]
. - אם מצאנו איבר כזה בכניסה ה של
L
, נקבעL[j + 1] = X[i]
. - אם לא, נקבע
L[1] = X[i]
.
- נחפש את האיבר הגדול ביותר ב ב
- נמצא את האיבר הגדול ביותר ב
L
שאינו , ונחזיר את האינדקס שלו כתשובה המבוקשת.
דוגמה: נניח ש כעת נעבור בלולאה על איברי
|
את המשפט הבא קל להוכיח באינדוקציה:
משפט: בסוף האיטרציה ה של הלולאה:
|
להלן הפסוודו-קוד המתאים:
1 L = Make-Array(n)
2 for i in [1, ..., n]
3 L[i] = ∞
4 for i in [1, ..., n]
5 j = Smaller-Index(L, X[i])
6 L[j + 1] = X[i]
7 max = 0
8 for i in [1, ..., n]
9 if L[i] > max and L[i] < ∞
10 max = L[i]
הנה הסבר לפסוודו-קוד:
- ב1-3 מאתחלים את
L
. קל לראות שהסיבוכיות לינארית. - ב4-6 מעדכנים את
L
על פי ההסבר שראינו למעלה. הפונקציהSmaller-Index
, שמימושה אינו מופיע כאן, ניתנת למימוש בקלות באופן דומה למה שראינו ב[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]] (שים לב שL
ממוין). הסיבוכיות היא . - ב7-10 מחפשים את המקסימום ב
L
. קל לראות שהסיבוכיות לינארית.