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

1. סקירה כללית

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

למשל, במערך שלהלן, למערך המשנה המודגש יש את הסכום המקסימלי (6):

במדריך זה נבחן שני פתרונות למציאת מערך המשנה המרבי במערך. אחד מהם נעצב איתו עַל) מורכבות זמן ומרחב.

2. אלגוריתם כוח הברוט

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

2.1. גִישָׁה

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

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

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

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

למרות זאת, האלגוריתם שלנו ימשיך למצוא את כל מערכי המשנה המתחילים במדדים שבין 0 ו n-1.

2.2. יישום

בואו נראה כעת כיצד נוכל ליישם פתרון זה ב- Java:

public int maxSubArray (int [] nums) {int n = nums.length; int maximumSubArraySum = מספר שלם.MIN_VALUE; התחלה int = 0; int end = 0; עבור (int left = 0; left <n; left ++) {int runningWindowSum = 0; עבור (int ימין = שמאל; ימין maximumSubArraySum) {maximumSubArraySum = runningWindowSum; התחלה = שמאלה; סוף = ימין; }}} logger.info ("נמצא מערך משנה מקסימאלי בין {} ל {}", התחלה, סוף); החזר maximumSubArraySum; }

כצפוי, אנו מעדכנים את maximumSubArraySum אם הסכום הנוכחי גדול מהסכום המקסימלי הקודם. יש לציין, לאחר מכן אנו גם מעדכנים את הַתחָלָה ו סוֹף כדי לגלות את מיקומי האינדקס של מערך המשנה הזה.

2.3. מוּרכָּבוּת

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

על ידי בדיקת הקוד אנו יכולים גם לראות שיש שני מקוננים ל לולאות. לכן, אנו יכולים להסיק כי מורכבות הזמן של אלגוריתם זה היא O (n2).

בחלקים המאוחרים יותר נפתור בעיה זו ב עַל) מורכבות באמצעות תכנות דינמי.

3. תכנות דינמי

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

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

3.1. האלגוריתם של קדאנה

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

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

3.2. גִישָׁה

בואו נבין את הבעיה הזו בצורה אחרת:

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

maximumSubArraySum = max_so_far + arr [n-1]

max_so_far הוא הסכום המקסימלי של מערך משנה שמסתיים באינדקס n-2. זה מוצג גם בתמונה לעיל.

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

maximumSubArraySum [n-2] = max_so_far [n-3] + arr [n-2]

לכן אנו יכולים להסיק כי:

maximumSubArraySum [i] = maximumSubArraySum [i-1] + arr [i]

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

maximumSubArraySum [i] = מקסימום (arr [i], maximumSubArraySum [i-1] + arr [i])

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

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

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

3.3. יישום

שוב, בואו נראה כיצד נוכל ליישם כעת את אלגוריתם Kadane בג'אווה, לפי הגישה לעיל:

public int maxSubArraySum (int [] arr) {int size = arr.length; התחלה int = 0; int end = 0; int maxSoFar = 0, maxEndingHere = 0; עבור (int i = 0; i maxEnding Here + arr [i]) {start = i; maxEndingHere = arr [i]; } אחר maxEndingHere = maxEnding Here + arr [i]; אם (maxSoFar <maxEndingHere) {maxSoFar = maxEndingHere; סוף = i; }} logger.info ("נמצא מערך משנה מקסימאלי בין {} ל {}", התחלה, סוף); החזר maxSoFar; }

הנה, עדכנו את הַתחָלָה ו סוֹף כדי למצוא את המדדים המקסימליים למערך המשנה.

3.4. מוּרכָּבוּת

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

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

4. מסקנה

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

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

כמו תמיד, קוד המקור המלא של המאמר זמין באתר GitHub.


$config[zx-auto] not found$config[zx-overlay] not found