האלגוריתם של Kadane

האלגוריתם של Kadane הוא האלגוריתם הטוב ביותר למציאת תת-המערך שסכומו המרבי מבין כל תתי-המערכים.

arr[]={-5, 4,  6, -3 , 4, -1}

במערך הזה, לתת-המערך {4, 6, -3 , 4 } יש את הסכום המרבי.

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

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

גישה

ברגע שאיבר בתת-המערך חיובי, במקרים האלה אפשר להוסיף אותו לסכום. 

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

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

1. צרו שני משתנים בשם maxSum ו-cumSum ואתחלו את שניהם ל-0.

2. הריצו לולאה מ-0 עד n פעמים.

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
  
}

3. חשבו את הסכום המצטבר של תת-המערך כך:

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
}

4. אם cumSum גדול מ-maxSum, שמרו אותו בו.

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
   
   if(cumSum>maxSum){
      maxSum=cumSum;
   }
}

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

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
   
   if(cumSum>maxSum){
      maxSum=cumSum;
   }
   
   if(cumSum<0){
      cumSum=0;
   }
}

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

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

ניתוח סיבוכיות זמן

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

למידע נוסף על האלגוריתם של Kadane

האלגוריתם של Kadane