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

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

1. נגדיר את הרישה ה$\displaystyle i$ של מחרוזת $\displaystyle X$ כ$\displaystyle X_{i}=x_{1},...,x_{i}$.‏
2. נגדיר כ$\displaystyle l(i)$ את אורך הLIS של $\displaystyle X_{i}$ שאיברה האחרון הוא $\displaystyle x_{i}$.
3. נשים לב ש:
   1. $\displaystyle \max _{1\leq i\leq n}[l(i)]$ הוא אורך הLIS של $\displaystyle X$.
   2. $\displaystyle l(i)$ מקיים את הנוסחה $\displaystyle l(i)=1+\max _{1\leq j<i,\;x_{j}\leq x_{i}}[l(j)]$.

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

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

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

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

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

משפט: בסוף האיטרציה ה$\displaystyle i$ של הלולאה: L ממוין. אם האיבר ה$\displaystyle j$ בL אינו $\displaystyle \infty$, אז יש תת-סידרה עולה ב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 ממוין). הסיבוכיות היא $\displaystyle \sum _{i=1}^{n}[O(\log(i))]=O(n\cdot \log(n))$.
3. ב7-10 מחפשים את המקסימום בL. קל לראות שהסיבוכיות לינארית.