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

תת-סדרה רצופה של הסדרה $(x_1, x_2,...,x_{n-1},x_n)$ הינה סדרה מהצורה $(x_i,x_{i+1},...,x_{k-1},x_k)$, עבור איזשהם $1 \leq i \leq k \leq n$. הציגו אלגוריתם שבהינתן סדרת מספרים שלמים $(x_1,...,x_n)$ מוצא בתוכה את תת-הסדרה הרצופה שסכומה מרבי. למשל, בסדרת הקלט $(-1,4,-3,5,-1,-1,1,-1)$ תת-הסדרה הרצופה שסכומה מרבי הינה $(4,-3,5)$ שסכומה $4-3+5=6$. על האלגוריתם המוצע לרוץ בזמן $\Theta(n)$, כשבניתוח זמן הריצה מניחים שכל פעולה אלמנטרית על מספרים (כגון חיבור, חיסור, השוואה) מתבצעת בזמן $\Theta(1)$.

רמז: הגדר $OPT(i)$ = הסכום המרבי של תת-סדרה רצופה המסתיימת ב-$x_i$, ובנה את הנסיגה $OPT(i) = \max(OPT(i-1) + x_i,\ x_i)$. עבור על הסדרה פעם אחת ועקוב אחר המקסימום הגלובלי.

פתרון: **הגדרת תת-בעיה:** יהי $OPT(i)$ הסכום המרבי של תת-סדרה רצופה **המסתיימת** באינדקס $i$ (כולל האפשרות לסכום $x_i$ בלבד). **נוסחת נסיגה:** $$OPT(1) = x_1$$ $$OPT(i) = \max(OPT(i-1) + x_i,\ x_i) \quad \text{לכל } i \geq 2$$ **נכונות:** תת-הסדרה המסתיימת ב-$x_i$ עם סכום מרבי היא: - הרחבה של התת-סדרה האופטימלית המסתיימת ב-$x_{i-1}$, אם $OPT(i-1) > 0$, או - $x_i$ בלבד, אם $OPT(i-1) \leq 0$. שני המקרים מתמצים ב-$OPT(i) = \max(OPT(i-1) + x_i,\ x_i)$. הסכום המרבי הכולל הוא $\max_{1 \leq i \leq n} OPT(i)$. **האלגוריתם:** ``` opt ← x_1 maxSub ← x_1 לכל i מ-2 עד n: opt ← max(opt + x_i, x_i) maxSub ← max(maxSub, opt) החזר maxSub ``` **סיבוכיות:** לולאה אחת של $n-1$ איטרציות, כל אחת מבצעת $O(1)$ פעולות. סה"כ: $\Theta(n)$. $\blacksquare$