אתגר תכנותי: מציאת תת מערך רציף שיש לו מכפלה מקסימלית

האתגר

נתון מערך של מספרים nums, וצריך למצוא תת מערך רציף שמכפלת איבריו היא הגבוהה ביותר.

לדוגמה:

nums = [4,5,-3,6]

התוצאה הצפויה 20 כי מכפלת האיברים [4,5] היא 20.

דוגמה נוספת:

nums = [-1,0,-2]

התוצאה הצפויה היא 0 כיוון שמכפלת האיברים -1 ב -2 אומנם נותנת 2 אבל הם אינם תת מערך רציף כיוון שמפריד ביניהם 0.

מערך רציף מורכב מאיברים שאין ביניהם הפרדה. ליהפך, האיברים מסודרים אחד אחרי השני ברצף.

הבעיה מזכירה בעיה דומה "תת מערך בעל סכום מירבי" שכדאי להתחיל מלפתור אותה כי היא יותר פשוטה.

אם ניקח לדוגמא את המערך:

nums = [3,4,-2,5]

גישה אחת תשתמש ב-brute force - לולאה מקוננת שתאתר את כל הצירופים האפשריים, ותמצא מתוכם את המכפלה המרבית. זו גישה אפשרית אך לא יעילה, ומטבע הדברים נרצה אלגוריתם יעיל יותר.

לצורך העניין, קיימות כמה אפשרויות:

• אם כל האיברים הם חיוביים (לבד מ 1) אז ככל שנכפול ביותר איברים תוצאת המכפלה תגדל.
• אם יש 0 במערך אז הוא יאפס את המכפלה.
• אם יש מספרים שליליים אז זה תלוי: אם ישנם מספר זוגי של איברים שליליים אז התוצאה תהיה חיובית אבל אם מספר אי-זוגי אז התוצאה תהיה שלילית.

אז מה עושים?

הרעיון הוא לעבור על המערך באמצעות לולאה איבר אחד בכל פעם, ובכל איטרציה לחשב את המכפלה המינימלית והמקסימלית. המכפלה המינימלית בגלל שכפל בערך שלילי יגרום לתוצאה מינימלית שיכול להיות שבאיטרציה הבאה תהפוך לחיובית אם כופלים בערך שלילי נוסף.

הדוגמה הבאה תדגים איך אפשר לעשות את זה. נתון מערך מספרים nums:

nums = [3,4,-2,5,-8]

האיבר הראשון הוא 3, מה שנותן ערך מינימלי ומקסימלי 3. לפיכך, נעדכן את הערך המקסימלי הגלובלי להיות גם כן 3.

כאן המקום להבהיר שדרושים לנו שלושה משתנים משתנים להם נקרא:

• min_local - ערך המינימום המחושב בכל איטרציה
• max_local - ערך המקסימום המחושב בכל איטרציה
• max_global - ערך המקסימום הגבוה ביותר מכל ערכי ה-max_local שמצא האלגוריתם

האיבר השני הוא 4 מה שנותן:

• ערך מינימלי 4 כי לוקחים את המינימום בין שלושה ערכים: האיבר הנוכחי 4, מכפלת המספר הנוכחי בערך המינימום מהצעד הקודם 4*3=12, ומכפלת המספר הנוכחי בערך המקסימום מהצעד הקודם 4*3=12

  min_local =min(num, min_local*num, max_local*num)

  min_local =min(4, 3*4, 3*4) = 4

• ערך מקסימלי 12 שהוא תוצאה של מכפלה של תת המערך [3,4] כי לוקחים את המקסימום בין שלושה ערכים: האיבר הנוכחי 4, מכפלת המספר הנוכחי במקסימום מהצעד הקודם, ומכפלת האיבר הנוכחי במינימום מהצעד הקודם

  max_local =max(num, min_local*num, max_local*num)

  max_local =max(4, 3*4, 3*4) = 12

• כיוון שהערך המקסימלי המקומי גבוה מערך המקסימום הגלובלי, נעדכן את המקסימום הגלובלי, שיהיה 12 במקום 3.

  max_global =max(max_global, max_local)

  max_global =max(3, 12) = 12

האיבר השלישי הוא -2 מה שנותן:

• ערך מינימלי מחושב -24

  min_local =min(num, min_local*num, max_local*num)

  min_local =min(-2, 4*(-2), 12*(-2)) = -24

• ערך מקסימלי מקומי -2

  max_local =max(num, min_local*num, max_local*num)

  max_local =max(-2, 4*(-2), 12*(-2)) = -2

  * יש לשים לב שאנחנו לוקחים את ערך המינימום מהצעד הקודם (4) ולא מהצעד הנוכחי (-24) בתור ערכו של min_local.

• הערך המקסימלי הגלובלי נותר ללא שינוי 12

  max_global =max(-2, 12) = 12

האיבר הרביעי הוא 5 מה שנותן:

• ערך מינימלי -120:

  min_local =min(num, min_local*num, max_local*num)

  min_local =min(5, 5*(-24), 5*(-2)) = -120

• ערך מקסימלי 5:

  max_local =max(num, min_local*num, max_local*num)

  max_local =max(5, (-24)*5,(-2)*5) = 5

• ערך מקסימלי גלובלי נותר ללא שינוי 12:

  max_global =max(5, 12) = 12

האיבר החמישי הוא -8 מה שנותן:

• ערך מינימלי -40 :

  min_local =min(num, min_local*num, max_local*num)

  min_local =min(-8, (-120)*(-8), 5*(-8)) = -40

• ערך מקסימלי מקומי 960 :

  max_local =max(num, min_local*num, max_local*num)

  max_local =max(-8, (-120)*(-8), 5*(-8)) = 960

  * 960 תוצאת המכפלה של -120 (ערך המינימום המקומי מהצעד הקודם) ב -8 מהצעד הנוכחי.

• בהתאם, נעדכן את הערך המקסימלי הגלובלי ל 960

התוצאה הסופית היא 960 כי השכלנו לקחת בחשבון את הערכים המינימליים בכל איטרציה ולא רק את המקסימליים.

יישום הקוד הלכה למעשה

"דיבורים כמו חול - תראה לי את הקוד"

הקוד להלן מיישם את ההסבר לעיל:

def max_product_contiguous_subarray(nums):
   if not nums: return None
   max_global = nums[0]
   min_local = max_local = max_global
   len_nums = len(nums)
   for idx in range(1, len_nums):
       num = nums[idx]
       candidates = (num, max_local * num, min_local * num)
       min_local = min(candidates)
       max_local = max(candidates)
       max_global = max(max_global, max_local)
   return max_global

נבדוק באמצעות מספר מקרי בוחן:

test_cases = [
   [[3,4,-2,5,-8], 960],
   [[1, 2, 3, 4, 5], 120],
   [[1, 2, -1, 3], 3],
   [[2, 3, -2, 4, -3], 144],
   [[-2, -1], 2],
   [[-3, 0, -2], 0],
   [[-3, 0, -2, 0], 0],
   [[-2, 0, -1, -3], 3],
   [[-1, -2, -3, -4], 24],
   [[-1, -2, -3], 6],
   [[-1, 0, -2, 4, -3], 24],
   [[] , None],
]

print(f"{'Result'.ljust(10)}{'Expected'.ljust(10)}{'Conclusion'}")
print(f"{'-'*10}{'-'*10}{'-'*10}")
for nums, expected in test_cases:
   res = max_product_contiguous_subarray(nums)
   conclusion = "😄" if res == expected else "😭"
   print(f"{str(res).ljust(10)}{str(expected).ljust(10)}{conclusion}")

print("Finito Programa")

נסביר את הפונקציה

• תחילה, נבדוק אם המערך ריק. אם כן, נחזיר None.
• נאתחל את המשתנים max_local, min_local, ו-max_global עם הערך של האיבר הראשון במערך.
• בכל איטרציה, נחשב את המועמדים החדשים עבור המכפלה המרבית והמינימלית: המכפלה של האיבר הנוכחי עם max_local ועם min_local, או האיבר עצמו.
• בסיום כל איטרציה, נעדכן את התוצאה המקסימלית בכל שלב עם המכפלה המרבית שנמצאה עד כה.
• לבסוף, הפונקציה תחזיר את הערך המקסימלי הגלובלי, max_global.

הערכת ביצועים

סיבוכיות הזמן היא לינארית O(N), כיוון שהפונקציה עוברת על כל איבר במערך בדיוק פעם אחת בתוך לולאה, ובכל איטרציה היא מבצעת פעולות השוואה וכפל הדורשות זמן קבוע לביצועם.

סיבוכיות המקום היא קבועה O(1) כיוון שהפונקציה משתמשת רק במשתנים המקבלים ערכים סקלריים.

סיכום

הבעיה של מציאת המכפלה המרבית בתת-מערך רציף דורשת חשיבה מחוץ לקופסא בעיקר בשל נוכחותם של מספרים שליליים ואפסים. הפתרון משתמש בשני משתנים המייצגים את המכפלה המקסימלית והמינימלית כדי לנצל את תוצאות המכפלות של מספרים שליליים. אלגוריתם זה מאפשר פתרון יעיל עם זמן ריצה של O(N), מה שהופך אותו לשימושי גם עבור מערכים גדולים.

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

תת מערך בעל סכום מירבי

אתגר תכנותי: מכפלת הכל לבד מהנוכחי

שיטת שני המצביעים לפתרון בעיות תכנותיות

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים