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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

נשתמש במספר סימונים ומשפטים פשוטים:

  1. נגדיר את הרישה ה של מחרוזת כ.‏
  2. נגדיר כ את אורך הLIS של שאיברה האחרון הוא .
  3. נשים לב ש:
    1. הוא אורך הLIS של .
    2. מקיים את הנוסחה .

בפתרון נשתמש במערך גלובלי L המתאר, בכניסה ה, את האיבר הקטן ביותר עד כה המסיים תת-סידרה עולה באורך .

אלה שלבי פעולות הפתרון:

  1. נאתחל את כל אחד מאיברי L ל.
  2. נעבור בלולאה, משמאל לימין, על איברי X. כשנגיע לאיבר ה:
    1. נחפש את האיבר הגדול ביותר ב בL[1], ..., L[i - 1] שאינו גדול מX[i].
    2. אם מצאנו איבר כזה בכניסה ה של L, נקבע L[j + 1] = X[i].
    3. אם לא, נקבע L[1] = X[i].
  3. נמצא את האיבר הגדול ביותר בL שאינו , ונחזיר את האינדקס שלו כתשובה המבוקשת.



דוגמה:

נניח שX == [1, 5, 2, 3]. תחילה נאתחל את המערך L, כך שL == [∞, ∞, ∞, ∞].

כעת נעבור בלולאה על איברי X:

  1. כשi == 1,‏ אז X[i] == 1. בL אין שום איבר קטן מ1 בתחום . נקבע, לכן, L[1] = 1. בשלב זה L = [1, ∞, ∞, ∞].
  2. כשi == 2,‏ אז X[i] == 5. האיבר הגדול ביותר בL שאינו גדול מ5, הוא 1 באינדקס 1. נקבע, לכן, L[2] = 5. בשלב זה L = [1, 5, ∞, ∞].
  3. כשi == 3,‏ אז X[i] == 2. האיבר הגדול ביותר בL שאינו גדול מ2, הוא 1 באינדקס 1. נקבע, לכן, L[2] = 2. בשלב זה L = [1, 2, ∞, ∞,].
  4. כשi == 4,‏ אז X[i] == 3. האיבר הגדול ביותר בL שאינו גדול מ4, הוא 2 באינדקס 2. נקבע, לכן, L[3] = 3. בשלב זה L = [1, 2, 3, ∞].האיבר הגדול ביותר בL שאינו , הוא 3. נחזיר, לכן, את האינדקס שלו - 3.


את המשפט הבא קל להוכיח באינדוקציה:



משפט:

בסוף האיטרציה ה של הלולאה:

  1. L ממוין.
  2. אם האיבר ה בL אינו , אז יש תת-סידרה עולה בX[1], ..., X[i] המסתיימת באיבר שערכו L[j].


להלן הפסוודו-קוד המתאים:

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. ב1-3 מאתחלים את L. קל לראות שהסיבוכיות לינארית.
  2. ב4-6 מעדכנים את L על פי ההסבר שראינו למעלה. הפונקציה Smaller-Index, שמימושה אינו מופיע כאן, ניתנת למימוש בקלות באופן דומה למה שראינו ב[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]] (שים לב שL ממוין). הסיבוכיות היא .
  3. ב7-10 מחפשים את המקסימום בL. קל לראות שהסיבוכיות לינארית.