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

המבנה הרקורסיבי

נגדיר כ$\displaystyle m(i)$ את המכפלה הגדולה ביותר האפשרית של תת-סידרה בדלנית של $\displaystyle [x_{1},...,x_{i}]$ (שים לב שתת-הסדרה אינה בהרכח משתמשת ב$\displaystyle x_{i}$).

משפט: $\displaystyle m(i)$ מקיימת את נוסחת הנסיגה הבאה: אם $\displaystyle i=1$, אז $\displaystyle m(i)=x_{1}$. אם $\displaystyle i=2$, אז $\displaystyle m(i)=\max\{x_{1},x_{2}\}$. אם $\displaystyle i>2$, אז $\displaystyle m(i)=\max\{m(i-1),m(i-2)\cdot x_{i}\}$.

הוכחה: נשים לב לנקודות הבאות:

1. אם $\displaystyle i=1$, אז בוודאי שנבחר באיבר הראשון (כל איבר הוא לפחות 1); נקבל בהכרח $\displaystyle x_{1}$.
2. אם $\displaystyle i=2$, אז בוודאי שנבחר באיבר הראשון או באיבר השני (כל איבר הוא לפחות 1); נקבל בהכרח $\displaystyle \max\{x_{1},x_{2}\}$.
3. אם $\displaystyle i>2$, אז או שנבחר ב$\displaystyle x_{i}$ או שלא (אלו שתי האפשרויות היחידות).
   • אם נבחר ב$\displaystyle x_{i}$, אז לא נוכל לבחור ב$\displaystyle x_{i-1}$; במקרה זה נרצה להכפיל את $\displaystyle x_{i}$ בתוצאה הטובה ביותר האפשרית עד $\displaystyle i-2$, שהיא $\displaystyle m(i-2)$.
   • אם לא נבחר את $\displaystyle x_{i}$, אז נרצה את תת-הסדרה הטובה ביותר עד $\displaystyle i-1$, שהיא, עפ"י ההגדרה, $\displaystyle m(i-1)$.

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

מימוש רקורסיבי נאיבי

להלן פסוודו-קוד המממש רעיון זה:

Max-Product(i)
1	if i == 1
2		return X[1]

3	if i == 2
4		return max(X[1], X[2])

6	guess-with = Max-Product(i - 2) * X[i]
7	guess-without = Max-Product(i - 1)
		
8	if guess-with > guess-without
9		return guess-with
10	else
11		return guess-without

קל לראות שסיבוכיות האלגוריתם גבוהה מדי. היא נתונה ע"י הפתרון לנוסחה $\displaystyle T(n)=T(n-1)+T(n-2)+O(1)$ (כלומר אקספוננציאלית, מפני שזו סדרת Fibonacci), וסיבתה היא הסיבה הקבועה: פתירת אותן תת-בעיות שוב ושוב.

שימוש בmemoization

להלן פסוודו-קוד יעיל יותר:

1	L = Make-Array(n)

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


Max-Product(i)
1	if L[i] != Nil
2		return L[i]

3	if i == 1
4		L[1] = X[1]
5		return L[1]

6	if i == 2
7		L[2] = max(X[1], X[2])
8		return L[2]

9	guess-with = Max-Product(i - 2) * X[i]
10	guess-without = Max-Product(i - 1)
		
11	if guess-with > guess-without
12		L[i] = guess-with
12		return L[i]
13	else
14		L[i] = guess-without
15		return L[i]

הדפסת האיברים

להלן פסוודו-קוד המאפשר גם הדפסת תת-הסדרה:

1	L = Make-Array(n)
2	U = Make-Array(n)

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


Max-Product(i)
1	if L[i] != Nil
2		return L[i]

3	if i == 1
4		L[1] = X[1]
5		U[1] = True
6		return L[1]

7	if i == 2
8		L[2] = max(X[1], X[2])
9		U[2] = X[2] == L[2]? True : False
10		return L[2]

11	guess-with = Max-Product(i - 2) * X[i]
12	guess-without = Max-Product(i - 1)
		
13	if guess-with > guess-without
14		L[i] = guess-with
15		U[i] = True
16		return L[i]
17	else
18		L[i] = guess-without
19		U[i] = False
20		return L[i]

המערך U מחזיק בכניסה ה$\displaystyle i$ את ההכרעה האם תת-הסדרה הטובה ביותר עד $\displaystyle i$ אכן משתמשת באיבר ה$\displaystyle i$ או לא. קטע הקוד הבא מראה כיצד להדפיס את האינדקסים של תת-הסידרה הטובה ביותר המסתיימת ב$\displaystyle i$.

Print-Seq(i)
1	if U[i] == True
2		Print-Seq(i - 2)
3		Print(i)
4		return
	
5	Print-Seq(i - 1)

כיצד נשתמש בקוד, אם כן?

1. נאתחל המשתנים הגלובליים, ונקרא לMax-Product(n).
2. נקרא לPrint-Seq(n).

ניתוח סיבוכיות

הסיבוכיות הכוללת הנה לינארית:

• מהתבוננות, ברור שהאתחול לינארי.
• הסיבוכיות של Max-Product(n) נתון על ידי $\displaystyle \sum _{i=1}^{n}[T'(i)]$, כאשר $\displaystyle T'(i)=O(1)$ הוא זמן הריצה של Max-Product(i) בהנחה שכל קריאה רקורסיבית היא $\displaystyle O(1)$ (ראו הניתוח בדג הסלמון).
• מהתבוננות, קל לראות שהדפסת האיברים היא $\displaystyle O(n)$.