Algoritmo di Kadane

Algoritmo di Kadane è il miglior algoritmo per trovare il sottarray che ha la somma massima tra tutti i sottarray.

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

In questo array, il sottarray {4, 6, -3 , 4 } ha la somma massima.

Il metodo più semplice per risolvere questo problema consiste nel trovare la somma di tutti i sottarray e poi stampare il sottarray con la somma massima. Ma, poiché richiede due iterazioni, la complessità temporale risulta dell'ordine di n² . 

Usando l'algoritmo di Kadane, la complessità temporale si riduce drasticamente.

Approccio

Non appena l'elemento del sottarray è positivo, in quei casi possiamo aggiungerlo alla somma. 

Pertanto, se la somma cumulativa di un sottarray qualsiasi risulta negativa, evita quella parte. 

Inizia dall'inizio e aggiungi gli elementi, memorizzando il massimo della somma cumulativa; se la somma diventa negativa, elimina quella parte e ricomincia dall'indice successivo.

1. Crea due variabili, maxSum e cumSum, e assegna a entrambe il valore 0.

2. Esegui un ciclo da 0 a n volte.

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

3. Calcola la somma cumulativa del sottarray come segue

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

4. Se cumSum è maggiore di maxSum, memorizzalo in maxSum.

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

5. Come abbiamo detto, se la somma cumulativa diventa negativa, evita quella parte. La somma massima che può produrre è già memorizzata nella variabile maxSum. Pertanto, se  cumSum diventa negativo, reimpostalo a 0 e ricomincia dall'indice successivo, come segue

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. Dopo aver iterato sull'intero array, la somma massima è memorizzata nella variabile maxSum.

Tieni presente che, se la somma massima del sottarray è negativa, dobbiamo modificare la funzione di conseguenza. Prova a farlo da solo

Analisi della complessità temporale

Poiché iteriamo sull'array una sola volta, la complessità temporale è O(n). Si tratta di un grande miglioramento rispetto all'approccio precedente.

Per saperne di più sull'algoritmo di Kadane

Algoritmo di Kadane