תחי ישראל - אין לנו ארץ אחרת

תחי ישראל -אין לנו ארץ אחרת

חידה תכנותית: תת מערך בעל סכום מירבי

מחבר:
בתאריך:

אתגר: מערך מקסימלי

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

לדוגמה, בהינתן המערך הבא:

[2, -4, 1, 2, -2]

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

[1, 2]

 

פתרון brute force

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

ניתן לקוד לדבר:

# The function takes an array of integers as input 
# and returns the maximum sum of subarray in the input array.
def max_subarray_sum(nums): 
    # Variable to store the maximum sum.
    global_max = -float("inf") 

    for idx in range(len(nums)):
        # Variable to store the sum of the current subarray.
        current_sum = 0 
        # Array containing the remaining elements in the array, 
        # starting at the current index.
        local_sub_array = nums[idx:] 
        for num in local_sub_array:
            # Add the current element to the current subarray sum.
            current_sum += num 
            # If the current subarray sum is greater than the global_max, 
            # update the global_max.
            if current_sum > global_max: 
                global_max = current_sum

    return global_max

נבדוק:

# Test cases
print(max_subarray_sum([2, -4, 1, 2, -2]))  # 3
print(max_subarray_sum([1, 2, 3, 4]))  # 10
print(max_subarray_sum([-1, -2, -3]))  # -1
print(max_subarray_sum([-2, -1, -3]))  # -1
print(max_subarray_sum([1]))  # 1
print(max_subarray_sum([-2, 1, 4, -3, 3, 2, -1]))  # 7

 

האיור הבא מדגים מה קורה בשלבים הראשונים של ריצת הלולאה המקוננת:

local sum vs global sum in the first iteration of the outer loop
  • מתחילים מתת מערך הכולל רק את האיבר הראשון וממנו מחשבים את ה-`local_sum` וה-`global_sum`. בריצה הבאה של הלולאה הפנימית, מרחיבים את תת המערך לשני פריטים. אח"כ לשלושה פריטים, ארבעה, וכיו"ב, עד שהלולאה הפנימית מגיעה לסוף המערך. בכל ריצה של הלולאה הפנימית מעדכנים את ה-`local_sum`, ואם ה-`local_sum` גדול מ-`global_max` אז מעדכנים את הסכום הגלובלי המקסימלי.

בפעם השנייה הלולאה החיצונית מתקדמת בפריט אחד. בהתאם הלולאה הפנימית מתחילה לרוץ מהאיבר השני של המערך:

local sum vs global sum in the second iteration of the outer loop
  • בכל פעם שהלולאה הפנימית רצה תת המערך המקומי מתארך בפריט אחד נוסף. מתת המערך המקומי מחשבים את ה-`local_sum`, ואם ה-`local_sum` גדול מ-`global_max` מעדכנים את הסכום הגלובלי.

בפעם השלישית הלולאה החיצונית מתקדמת בפריט אחד, ואז הלולאה הפנימית מתחילה לרוץ מהאיבר השלישי של המערך.

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

הפתרון מתאפיין בסיבוכיות זמן O(N^2) וסיבוכיות מקום O(N):

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

 

מציאת תת המערך הרציף שסכום פריטיו הוא הגבוה ביותר באמצעות אלגוריתם Kadane

אף שקל לחשוב על פתרון brute force קיימת דרך יעילה יותר לפתור את הבעיה והיא משתמשת באלגוריתם Kadane.

 

אלגוריתם Kadane מוצא את תת המערך שסכומו הוא הגבוה ביותר.ביישום של האלגוריתם המשתנה `global_max` הוא סכום תת המערך הגבוה ביותר. האלגוריתם עובר פעם אחת על המערך מתחילתו ועד סופו, ועבור כל פריט הוא מוצא את הערך המקסימלי המקומי `current_sum` על ידי השוואת חיבור סכום תת המערך המסתיים בפריט שלפני הנוכחי (M באיור) עם הפריט הנוכחי (M+X) עם הפריט הנוכחי X, ולקיחת הערך הגבוה מבין השניים. אם הגבוה מבין השניים הוא M+X אז הוא מרחיב את תת המערך, ואם X אז הוא מתחיל תת מערך חדש ב-X. אם הערך של `current_sum` גבוה מ-`global_max` אז מעדכנים את `global_max`.

Key idea of the Kadane algorithm - MAX((M+X), X)

עבור הפריט הראשון המקסימום הגלובלי והמקומי הוא 2 כי זה ערך הפריט הראשון.

Kadane algo first item local and global_max are 2

עבור הפריט השני המקסימום המקומי הוא ערך הפריט הנוכחי (-4) או הערך הנצבר של תת המערך בתוספת הפריט הנוכחי (2+(-4)):

max(-4, 2+(-4)) = -2
  • המקסימום המקומי (-2) נמוך מהמקסימום הגלובלי (2) ולפיכך אין צורך לעדכן את המקסימום הגלובלי.
Kadane algo second item local = -4 and global = 2

עבור הפריט השלישי המקסימום המקומי הוא ערך הפריט השלישי (1) או הערך הנצבר של תת המערך בתוספת הפריט הנוכחי (1+(-2)):

max(1, 1+(-2)) = 1
  • המקסימום המקומי (1) נמוך מהמקסימום הגלובלי (2) ולכן אין צורך לעדכן את המקסימום הגלובלי.
Kadane algo third item local = 1 and global = 2

עבור הפריט הרביעי המקסימום הוא ערך הפריט הרביעי (2) או הערך הנצבר של תת המערך בתוספת הפריט הנוכחי (2+1):

max(2, 1+2) = 3
  • המקסימום המקומי (3) גבוה מהמקסימום הגלובלי (2) ולכן נעדכן את ערך המקסימום הגלובלי.
Kadane algo 4th item local = 3 and global = 3

עבור הפריט החמישי המקסימום הוא ערך הפריט החמישי (-2) או הערך הנצבר של תת המערך בתוספת הפריט הנוכחי (-2+3):

max(-2, (-2+3)) = 1
  • המקסימום המקומי (1) נמוך מהמקסימום הגלובלי (3) ולכן אין צורך לעדכן את המקסימום הגלובלי.
Kadane algo last array item local = 1 and global is still 3

אחרי שעברנו פעם אחת בלבד על המערך באמצעות אלגוריתם Kadane קיבלנו את התשובה שהמקסימום הגלובלי הוא 3.

 

הקוד הבא מיישם את אלגוריתם Kadane למציאת סכום תת המערך הגבוה ביותר:

def max_subarray_sum(nums):
    if not nums:
        return None

    # Initialize the global maximum and current sum to the value of the first array element
    global_max = nums[0] 
    current_sum = nums[0] 

    len_nums = len(nums)
    for idx in range(1, len_nums):
        num = nums[idx]

        # Update the current sum by taking the maximum between the current 
        # element and the sum of the current element when added to the current sum
        current_sum = max(num, num + current_sum)
        
        # Update the global maximum by taking the maximum between 
        # the global maximum and the current maximum
        global_max = max(global_max, current_sum)


    return global_max

נבדוק:

# Test cases
print(max_subarray_sum([2, -4, 1, 2, -2]))  # 3
print(max_subarray_sum([1, 2, 3, 4]))  # 10
print(max_subarray_sum([-1, -2, -3]))  # -1
print(max_subarray_sum([-2, -1, -3]))  # -1
print(max_subarray_sum([1]))  # 1
print(max_subarray_sum([-2, 1, 4, -3, 3, 2, -1]))  # 7
print(max_subarray_sum([]))  # None

הפונקציה max_subarray_sum() לוקחת מערך של מספרים שלמים כקלט ומחזירה את הסכום המקסימלי של תת מערך רצוף שהוא חלק ממערך הקלט.

הפונקציה פועלת באופן הבא:

  1. תחילה היא בודקת אם מערך הקלט ריק. אם זה המצב, הפונקציה מחזירה None.

  2. אחרת, הפונקציה מאתחלת שני משתנים: `global_max` ו-`current_sum` שערכם ההתחלתי שווה לפריט הראשון (אינדקס 0) במערך הקלט:

    • `global_max` - יאחסן את הסכום המקסימלי שנמצא עד כה, וזה גם מה שהפונקציה תחזיר.

    • `current_sum` יאחסן את הסכום של תת המערך הנוכחי.

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

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

    • מעדכנת את `global_max` על ידי מציאת המקסימום בין `global_max` ו-`current_sum`.

  4. לאחר מעבר על המערך כולו, הפונקציה מחזירה את `global_max`.

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

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

 

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

חידה תכנותית: twoSum

טכניקת חלון ההזזה sliding window לפתרון בעיות ברצפים

פתרון בעיות אופטימיזיציה באמצעות אלגוריתם חמדן

 

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

 

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

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

 

 

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

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

שימו לב! הסקריפטים במדריכים מיועדים למטרות לימוד בלבד. כשאתם עובדים על הפרויקטים שלכם אתם צריכים להשתמש בספריות וסביבות פיתוח מוכחות, מהירות ובטוחות.

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

השימוש שלך באתר מהווה ראייה להסכמתך עם הכללים והתקנות שנוסחו בהסכם תנאי השימוש.

הוסף תגובה חדשה

 

 

ענה על השאלה הפשוטה הבאה כתנאי להוספת תגובה:

איך קוראים בעברית לצ`ופצ`יק של הקומקום?