Algorytm Kadane’a

Algorytm Kadane’a to najlepszy algorytm do znalezienia podtablicy o największej sumie spośród wszystkich podtablic.

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

W tej tablicy podtablica {4, 6, -3 , 4 } ma największą sumę.

Najprostsze podejście do rozwiązania tego problemu polega na obliczeniu sumy wszystkich podtablic, a następnie wypisaniu podtablicy o największej sumie. Jednak ponieważ wymaga to dwóch iteracji, złożoność czasowa wynosi n² . 

Zastosowanie algorytmu Kadane’a znacznie zmniejsza złożoność czasową.

Podejście

Gdy element podtablicy jest dodatni, możemy dodać go do sumy. 

Dlatego jeśli suma skumulowana dowolnej podtablicy staje się ujemna, pomiń tę część. 

Zacznij od początku i dodawaj elementy, zapisując największą sumę skumulowaną. Jeśli suma stanie się ujemna, usuń tę część i zacznij ponownie od następnego indeksu.

1. Utwórz dwie zmienne o nazwach maxSum i cumSum i przypisz obu wartość 0.

2. Uruchom pętlę od 0 do n razy.

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

3. Oblicz sumę skumulowaną podtablicy w następujący sposób:

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

4. Jeśli cumSum jest większe niż maxSum, zapisz tę wartość w maxSum.

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

5. Jak omówiliśmy, jeśli suma skumulowana stanie się ujemna, pomiń tę część. Największa suma, jaką może ona utworzyć, jest już zapisana w zmiennej maxSum. Dlatego jeśli  cumSum stanie się ujemne, ponownie przypisz mu wartość 0 i zacznij od następnego indeksu w następujący sposób:

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. Po przejściu przez całą tablicę największa suma jest zapisana w zmiennej maxSum.

Pamiętaj, że jeśli największa suma podtablicy jest ujemna, musimy odpowiednio zmodyfikować funkcję. Spróbuj samodzielnie.

Analiza złożoności czasowej

Ponieważ przechodzimy przez tablicę tylko raz, złożoność czasowa wynosi O(n). To znaczna poprawa w porównaniu z poprzednim podejściem.

Więcej informacji o algorytmie Kadane’a:

Algorytm Kadane’a