בעיית תת-מערך מקסימלית זהה לבעיית הפרוסה המקסימלית. מדריך זה דן בבעיה עם קידוד ב-C++. השאלה היא: מהו הסכום המקסימלי של כל רצף אפשרי של מספרים עוקבים בתוך מערך? זה יכול להיות כל המערך. בעיה זו והפתרון שלה בכל שפה, מכונה בעיית המשנה המקסימלית. למערך יכולים להיות מספרים שליליים אפשריים.
הפתרון צריך להיות יעיל. זה צריך להיות בעל מורכבות הזמן המהירה ביותר. נכון לעכשיו, האלגוריתם המהיר ביותר לפתרון ידוע בקהילה המדעית בשם האלגוריתם של Kadane. מאמר זה מסביר את האלגוריתם של Kadane עם C++.
דוגמאות לנתונים
שקול את הווקטור הבא (מערך):
וֶקטוֹר < int > א = { 5 , - 7 , 3 , 5 , - שתיים , 4 , - 1 } ;
הפרוסה (תת-מערך) עם הסכום המקסימלי הוא הרצף, {3, 5, -2, 4}, שנותן סכום של 10. שום רצף אפשרי אחר, אפילו המערך כולו, לא ייתן סכום של עד הערך של 10. המערך כולו נותן סכום של 7, שאינו הסכום המקסימלי.
שקול את הווקטור הבא:
וֶקטוֹר < int > B = { - שתיים , 1 , - 3 , 4 , - 1 , שתיים , 1 , - 5 , 4 } ;
הפרוסה (תת-מערך) עם הסכום המקסימלי הוא הרצף, {4, −1, 2, 1} שנותן סכום של 6. שימו לב שיכולים להיות מספרים שליליים בתוך מערך המשנה לסכום מקסימלי.
שקול את הווקטור הבא:
וֶקטוֹר < int > C = { 3 , שתיים , - 6 , 4 , 0 } ;
הפרוסה (תת-מערך) עם הסכום המקסימלי הוא הרצף, {3, 2} שנותן סכום של 5.
שקול את הווקטור הבא:
וֶקטוֹר < int > D = { 3 , שתיים , 6 , - 1 , 4 , 5 , - 1 , שתיים } ;
תת-מערך עם הסכום המקסימלי הוא הרצף, {3, 2, 6, -1, 4, 5, -1, 2} שנותן סכום של 20. זהו המערך כולו.
שקול את הווקטור הבא:
וֶקטוֹר < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , חֲמֵשׁ עֶשׂרֵה , 4 , - 8 , - חֲמֵשׁ עֶשׂרֵה , - 22 } ;
יש שני מערכי משנה עם סכומים מקסימליים, כאן. הסכום הגבוה יותר הוא זה שנחשב כפתרון (תשובה) לבעיית המשנה המקסימלית. מערכי המשנה הם: {5, 7} עם סכום של 12, ו-{6, 5, 10, -5, 15, 4} עם סכום של 35. כמובן, הפרוסה עם הסכום של 35, היא התשובה.
שקול את הווקטור הבא:
וֶקטוֹר < int > F = { - 4 , 10 , חֲמֵשׁ עֶשׂרֵה , 9 , - 5 , - עשרים , - 3 , - 12 , - 3 , 4 , 6 , 3 , שתיים , 8 , 3 , - 5 , - שתיים } ;
ישנם שני מערכי משנה עם סכומים מקסימליים. הסכום הגבוה יותר הוא זה שנחשב כפתרון לבעיית המשנה המקסימלית. מערכי המשנה הם: {10, 15, 9} עם סכום של 34, ו-{4, 6, 3, 2, 8, 3} עם סכום של 26. כמובן, הפרוסה עם הסכום של 34 היא התשובה כי הבעיה היא לחפש את תת המערך עם הסכום הגבוה ביותר ולא את תת המערך עם הסכום הגבוה יותר.
פיתוח האלגוריתם של קדן
המידע בחלק זה של ההדרכה אינו היצירה המקורית של Kadane. זוהי דרכו של המחבר ללמד את האלגוריתם של קדן. אחד מהווקטורים לעיל, עם הסכומים הרצים שלו, נמצא בטבלה זו:
| נתונים | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | חֲמֵשׁ עֶשׂרֵה | 4 | -8 | -חֲמֵשׁ עֶשׂרֵה | -22 |
| סכום כולל | 5 | 12 | 8 | -שתיים | -8 | -שתיים | 3 | 13 | 8 | 23 | 27 | עשרים ואחת | 16 | -6 |
| אינדקס | 0 | 1 | שתיים | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | אחד עשר | 12 | 13 |
Running Total עבור אינדקס הוא הסכום של כל הערכים הקודמים כולל זה של האינדקס. יש כאן שני רצפים עם סכומים מקסימליים. הם {5, 7}, שנותן סכום של 12, ו-{6, 5, 10, -5, 15, 4}, שנותן סכום של 35. הרצף שנותן סכום של 35 הוא הרצוי .
שימו לב שעבור הסיכומים הרצים, יש שתי פסגות שהן הערכים, 12 ו-27. השיאים האלה תואמים לאינדקסים האחרונים של שני הרצפים.
לכן, הרעיון של האלגוריתם של Kadane הוא לבצע את הסכום הכולל תוך השוואת הסכומים המקסימליים כפי שהם נתקלים, נע משמאל לימין במערך הנתון.
וקטור נוסף מלמעלה, עם הסכומים הרצים שלו, נמצא בטבלה זו:
ישנם שני רצפים עם סכומים מקסימליים. הם {10, 15, 9}, מה שנותן סכום של 34; ו{4, 6, 3, 2, 8, 3} שנותן סכום של 26. הרצף שנותן את הסכום של 34, הוא הרצוי.
שימו לב שעבור הסיכומים הרצים, ישנם שני פסגות שהם הערכים, 30 ו-13. פסגות אלו תואמות את האינדקסים האחרונים של שני הרצפים.
שוב, הרעיון של האלגוריתם של Kadane הוא לבצע את הסכום הכולל תוך השוואת הסכומים המקסימליים כפי שהם נתקלים, נע משמאל לימין במערך הנתון.
קוד על ידי האלגוריתם של Kadane ב-C++
הקוד שניתן בחלק זה של המאמר אינו בהכרח מה שקדן השתמש בו. עם זאת, זה לפי האלגוריתם שלו. התוכנית כמו הרבה תוכניות C++ אחרות, תתחיל ב:
#include#include
שימוש במרחב שמות std;
יש הכללה של ספריית iostream, שאחראית על קלט ופלט. נעשה שימוש במרחב השמות הסטנדרטי.
הרעיון של האלגוריתם של Kadane הוא לקבל את הסכום הרצוי תוך השוואת הסכומים המקסימליים כפי שהם נתקלים בהם, נע משמאל לימין במערך הנתון. הפונקציה של האלגוריתם היא:
int maxSunArray ( וֶקטוֹר < int > & א ) {int N = A.size ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
ל ( int אני = 1 ; אני < נ; i++ ) {
int tempRunTotal = runTotal + A [ אני ] ; // יכול להיות קטן מ-A [ אני ]
אם ( א [ אני ] > tempRunTotal )
runTotal = A [ אני ] ; // ב מקרה א [ אני ] הוא גדול יותר מסך הריצה
אַחֵר
runTotal = tempRunTotal;
אם ( runTotal > maxAmount ) // השוואה בין כל הסכומים המקסימליים
maxSum = runTotal;
}
לַחֲזוֹר maxAmount;
}
הגודל, N של המערך הנתון (וקטור) נקבע. המשתנה, maxSum הוא אחד מהסכומים המקסימליים האפשריים. למערך יש לפחות סכום מקסימלי אחד. המשתנה, runTotal מייצג את הסכום הרצוי בכל אינדקס. שניהם מאותחלים עם הערך הראשון של המערך. באלגוריתם זה, אם הערך הבא במערך גדול מהסך הכל הריצה אז הערך הבא יהפוך לסך הרץ החדש.
יש לולאה ראשית אחת. הסריקה מתחילה מ-1 ולא מאפס בגלל האתחול של המשתנים, maxSum ו-runTotal ל-A[0] שהם האלמנט הראשון של המערך הנתון.
בלולאת for, ההצהרה הראשונה קובעת סך רץ זמני על ידי הוספת הערך הנוכחי לסכום המצטבר של כל הערכים הקודמים.
לאחר מכן, יש מבנה if/else. אם הערך הנוכחי לבדו גדול מהסך השוטף עד כה, אז הערך הבודד הזה הופך לסך השוטף. זה שימושי במיוחד אם כל הערכים במערך הנתון הם שליליים. במקרה זה, הערך השלילי הגבוה ביותר לבדו יהפוך לערך המקסימלי (התשובה). אם הערך הנוכחי לבדו אינו גדול מהסך השוטף הזמני עד כה, אזי הסכום הרץ הופך לסך הרץ הקודם בתוספת הערך הנוכחי, - זה החלק האחר של המבנה if/else.
קטע הקוד האחרון ב-for-loop בוחר בין כל סכום מקסימלי קודם עבור רצף קודם (משנה-מערך) לבין כל סכום מקסימלי נוכחי עבור רצף נוכחי. לכן נבחר הערך הגבוה יותר. יכול להיות יותר מסכום תת-מערך מרבי אחד. שימו לב שהסך הכולל יעלה ויירד, כאשר המערך נסרק משמאל לימין. הוא נופל כשהוא פוגש ערכים שליליים.
סכום המשנה המקסימלי הנבחר הסופי מוחזר לאחר לולאת for.
התוכן עבור פונקציה ראשית מתאימה של C++, עבור פונקציית האלגוריתם של Kadane הוא:
וֶקטוֹר < int > א = { 5 , - 7 , 3 , 5 , - שתיים , 4 , - 1 } ; // { 3 , 5 , - שתיים , 4 } - > 10int ret1 = maxSunArray ( א ) ;
cout << ret1 << endl;
וֶקטוֹר < int > B = { - שתיים , 1 , - 3 , 4 , - 1 , שתיים , 1 , - 5 , 4 } ; // { 4 , - 1 , שתיים , 1 } - > 6
int ret2 = maxSunArray ( ב ) ;
cout << ret2 << endl;
וֶקטוֹר < int > C = { 3 , שתיים , - 6 , 4 , 0 } ; // { 3 , שתיים } - > 5
int ret3 = maxSunArray ( ג ) ;
cout << ret3 << endl;
וֶקטוֹר < int > D = { 3 , שתיים , 6 , - 1 , 4 , 5 , - 1 , שתיים } ; // { 3 , שתיים , 6 , - 1 , 4 , 5 , - 1 , שתיים } - > 5
int ret4 = maxSunArray ( ד ) ;
cout << נטו4 << endl;
וֶקטוֹר < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , חֲמֵשׁ עֶשׂרֵה , 4 , - 8 , - חֲמֵשׁ עֶשׂרֵה , - 22 } ; // { 6 , 5 , 10 , - 5 , חֲמֵשׁ עֶשׂרֵה , 4 } - > 35
int ret5 = maxSunArray ( ו ) ;
cout << ret5 << endl;
וֶקטוֹר < int > F = { - 4 , 10 , חֲמֵשׁ עֶשׂרֵה , 9 , - 5 , - עשרים , - 3 , - 12 , - 3 , 4 , 6 , 3 , שתיים , 8 , 3 , - 5 , - שתיים } ; // { 10 , חֲמֵשׁ עֶשׂרֵה , 9 } - > 3. 4
int ret6 = maxSunArray ( ו ) ;
cout << נכון 6 << endl;
עם זה, הפלט יהיה:
10
6
5
עשרים
35
3. 4
כל תשובה בשורה כאן, מתאימה למערך נתון, לפי הסדר.
סיכום
מורכבות הזמן עבור האלגוריתם של Kadane היא O(n), כאשר n הוא מספר האלמנטים במערך הנתון. המורכבות הפעם היא המהירה ביותר לבעיית המשנה המקסימלית. ישנם אלגוריתמים אחרים שהם איטיים יותר. הרעיון של האלגוריתם של Kadane הוא לבצע את הסכום הרצוי, תוך השוואת הסכומים המקסימליים כפי שהם נתקלים בהם, לנוע משמאל לימין במערך הנתון. אם הערך הנוכחי לבדו גדול מהסך השוטף עד כה, אז הערך הבודד הזה הופך לסך השוטף החדש. אחרת, הסכום הרצוי החדש הוא הסכום הרצוי הקודם בתוספת האלמנט הנוכחי, כצפוי, כאשר המערך הנתון נסרק.
יכול להיות יותר מסכום מקסימלי אחד, עבור מערכי משנה אפשריים שונים. הסכום המקסימלי הגבוה ביותר, עבור כל מערכי המשנה האפשריים, נבחר.
מהם המדדים המגבילים לטווח הסכום המקסימלי הנבחר? – זה דיון לזמן אחר!
כריס