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

נגדיר את אורך $\displaystyle X$ כ$\displaystyle n$.

1. בפסוודו-קוד הבא, קריאה לLIS-Length(i) תחזיר את אורך הLIS שאיברו האחרון הוא

   האיבר ה$\displaystyle i$ בסדרה. (כדי למצוא את אורך הLIS הכללי, יש לבדוק את המקסימום
   בלולאה).
 

1		L = Make-Array(n)

2		for i in [1, ..., n]
3			L[i] = Nil


LIS-Length(i)
1		'''if L[i] == Nil'''
2			if i == 1
3				'''L[i] = 1'''
4				return 1
	
5			'''L[i] =''' max = 1
	
6			for j in [1, ..., i - 1]
7				if X[j] ≤ X[i]
8					guess = 1 + LIS-Length(j)
9					if guess > max
10						'''L[i] =''' max = guess

11		'''return L[i]'''

 1-3 מייצרות מערך (גלובלי) שכל אחד מאיבריו מאותחל לNil.‏ 6-10 של LIS-Length, פועלות בדיוק לפי נוסחת הנסיגה לאורך הLIS שכבר ראינו (ושאת נכונותה כבר
   הראינו). המערך L, בפרט ב1 של
   LIS-Length, מטפלות במצב בו הפונקציה נקראת עם פרמטרים שאתם היא כבר נקראה
   בעבר.
 נעבור בלולאה, ונקרא לLIS-Length(1),‏‏‏ LIS-Length(2),‏ ..., LIS-Length(n) (לפי סדר זה).
   נשמור את המקסימום המתקבל מהקריאות, ואת האינדקס בו התקבל מקסימום זה. בגלל הmemoization, ברור שLIS-Length(i) היא $\displaystyle \Theta (i)$ (כי $\displaystyle 8$ היא $\displaystyle O(1)$). לכן זמן הריצה הוא $\displaystyle \sum _{i=1}^{n}[\Theta (i)]=\Theta (n^{2})$.‏ ‏ חוץ מכך ישנו האתחול 1-3 שאורך $\displaystyle \Theta (n)$. הזמן הכולל, לכן, הוא $\displaystyle \Theta (n^{2})$.

1. ראשית נשנה מעט את הפסוודו-קוד הקודם. השינויים מסומנים כך.

1		L = Make-Array(n)
2		'''P = Make-Array(n)'''

3		for i in [1, ..., n]
4			L[i] = Nil


LIS-Length(i)
1		if L[i] == Nil
2			if i == 1
3				return 1

4			L[i] = 1
5			'''P[i] = 0'''

6			for j in [1, ..., i - 1]			
7				if X[j] ≤ X[i]
8					if 1 + LIS-Length(j) > L[i]
9						L[i] = 1 + LIS-Length(j)
10						'''P[i] = j'''

11		return L[i]

 המערך הגלובלי P מתאר בכניסה ה$\displaystyle i$ את אינדקס האיבר
   הקודם בסדרה.
 בפסוודו-קוד הבא, קריאה לPrint-LIS(i) תדפיס את הLIS שאיברו האחרון הוא האיבר
   ה$\displaystyle i$ בסדרה. כדי להדפיס את הLIS הכללי, יש לקרוא לו עם האינדקס שמצאנו
   בסעיף הקודם.
 

Print-LIS(i)
1		if i > 0
2			Print-LIS(P[i])

3		Print(i)

 קל לראות שהסיבוכיות עדיין $\displaystyle \Theta (n^{2})$: השינויים בLIS-Length אינם משנים את סיבוכיותה; כל קריאה לPrint-LIS(i) מורידה הארגומנט שלה ב1, ולכן היא יכולה להיקרא לכל היותר $\displaystyle n$ פעמים. הסיבוכיות, לכן, היא $\displaystyle \Theta (n^{2})$ + $\displaystyle O(n)$ = $\displaystyle \Theta (n^{2})$.