שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2011 - תכנות דינמי

יהי $A$ מערך של $n$ המוניים (לא מיוחדים). הגדר זמן ריצה של $O(1)$ בלא קאי, עיבודים הפונקציה הוקרא לאחסון הנתונים ומחזיר $(L,R)$ שתיית שונות שלמים בעיניים $1 \leq L \leq R \leq n$ כך שסכום המערך מתא $L$ עד $R$ מקסימום אפשרי בכל קנקנים של המערך. בקץ הבעיה רחבה דיגום סדרה משנה ברציפות עם סימן בדיקה $O(1)$ (המספיק בה בחוקי הבחינה בעמידת תנאים תיטת המערך הנתונה).

רמז: עבור על המערך במעבר יחיד. בכל צעד, חשב את הסכום המקסימלי של תת-מערך המסתיים באינדקס הנוכחי, והשתמש בתוצאה זו כדי לעדכן את הסכום המקסימלי הכולל שנמצא עד כה.

פתרון: הבעיה המתוארת, על אף הניסוח המשובש, היא בעיה קלאסית במדעי המחשב הידועה כבעיית **תת-המערך הרציף בעל הסכום המקסימלי** (Maximum Subarray Problem). המטרה היא למצוא תת-מערך רציף $A[L..R]$ במערך נתון $A$ כך שהסכום $\sum_{i=L}^{R} A[i]$ הוא הגדול ביותר האפשרי. ניתן לפתור בעיה זו ביעילות באמצעות **תכנות דינמי**, באלגוריתם הידוע כ**אלגוריתם של קדן (Kadane's Algorithm)**.\n\n**הרעיון המרכזי:**\nהאלגוריתם סורק את המערך משמאל לימין במעבר יחיד. בכל שלב $i$, אנו מחשבים את הסכום המקסימלי של תת-מערך רציף *המסתיים באינדקס $i$*. נסמן סכום זה ב-$current\_max$.\nכדי לחשב את $current\_max$ עבור האינדקס $i$, יש שתי אפשרויות:\n1. תת-המערך המקסימלי שמסתיים ב-$i$ מורכב מהאיבר $A[i]$ בלבד.\n2. תת-המערך המקסימלי שמסתיים ב-$i$ הוא הרחבה של תת-המערך המקסימלי שהסתיים ב-$i-1$, על ידי הוספת $A[i]$.\n\nלכן, מתקיימת **נוסחת הנסיגה** הבאה:\n$current\_max_i = \max(A[i], current\_max_{i-1} + A[i])$\n\nבמקביל, אנו שומרים משתנה נוסף, $max\_so\_far$, אשר מחזיק את הסכום המקסימלי שנמצא עד כה, בכל אינדקס שהוא. לאחר כל חישוב של $current\_max_i$, אנו מעדכנים את $max\_so\_far$:\n$max\_so\_far_i = \max(max\_so\_far_{i-1}, current\_max_i)$\n\nכדי להחזיר את האינדקסים $(L, R)$, עלינו לעקוב אחר נקודות ההתחלה והסוף של תתי-המערכים המתאימים ל-$current\_max$ ול-$max\_so\_far$.\n\n**אלגוריתם:**\n1. אתחל:\n - `max_so_far = A[1]` (הסכום המקסימלי הכולל)\n - `current_max = A[1]` (הסכום המקסימלי שמסתיים באינדקס הנוכחי)\n - `best_L = 1`, `best_R = 1` (האינדקסים של הפתרון הטוב ביותר עד כה)\n - `current_L = 1` (אינדקס ההתחלה של המערך הנוכחי)\n2. עבור `i` מ-2 עד `n`:\n א. אם `A[i] > current_max + A[i]`:\n - `current_max = A[i]`\n - `current_L = i`\n ב. אחרת:\n - `current_max = current_max + A[i]`\n ג. אם `current_max > max_so_far`:\n - `max_so_far = current_max`\n - `best_L = current_L`\n - `best_R = i`\n3. החזר את `(best_L, best_R)`.\n\n**ניתוח סיבוכיות:**\n- **סיבוכיות זמן:** האלגוריתם מבצע מעבר יחיד על המערך $A$ בגודל $n$. כל פעולה בתוך הלולאה לוקחת זמן קבוע, $O(1)$. לכן, **סיבוכיות הזמן הכוללת היא $O(n)$**.\n- **סיבוכיות מקום:** האלגוריתם משתמש במספר קבוע של משתנים נוספים (`max_so_far`, `current_max`, וכו') ללא תלות בגודל הקלט $n$. לכן, **סיבוכיות המקום (הנוספת) היא $O(1)$**.\n\n**הוכחת נכונות (באינדוקציה):**\n**טענה:** לכל $k \geq 1$, לאחר איטרציה $k$ של הלולאה, המשתנה `current_max` מכיל את הסכום המקסימלי של תת-מערך רציף המסתיים באינדקס $k$, והמשתנה `max_so_far` מכיל את הסכום המקסימלי של תת-מערך רציף כלשהו בתוך $A[1..k]$.\n**בסיס האינדוקציה ($k=1$):** לפני תחילת הלולאה, מאתחלים `current_max = A[1]` ו-`max_so_far = A[1]`. זה נכון כי תת-המערך היחיד ב-$A[1..1]$ הוא $A[1]$ עצמו.\n**צעד האינדוקציה:** נניח שהטענה נכונה עבור $k-1$. באיטרציה ה-$k$, אנו מחשבים את `current_max` החדש. תת-מערך רציף מקסימלי המסיים ב-$k$ חייב לכלול את $A[k]$. הוא או מורכב מ-$A[k]$ בלבד, או מהרחבה של תת-מערך רציף מקסימלי המסיים ב-$k-1$. סכומו הוא לכן $\max(A[k], \text{sum}(S_{k-1}) + A[k])$, כאשר $S_{k-1}$ הוא תת-המערך הרציף המקסימלי המסיים ב-$k-1$. לפי הנחת האינדוקציה, סכום זה הוא `current_max` מהאיטרציה הקודמת. לכן, עדכון `current_max` ל-$\max(A[k], \text{current\_max} + A[k])$ הוא נכון. לאחר מכן, `max_so_far` מתעדכן להיות המקסימום בין ערכו הקודם (הסכום המקסימלי ב-$A[1..k-1]$) לבין `current_max` החדש (הסכום המקסימלי המסיים ב-$k$). זה מבטיח ש-`max_so_far` יכיל את הסכום המקסימלי ב-$A[1..k]$. $\blacksquare$