Trovare il sottoarray di somma massima in C

Trovare il sottoarray di somma massima è un problema classico in informatica, noto anche come problema del massimo sottoarray o problema di Kadane. Questo problema consiste nel trovare il sottoarray contiguo all'interno di un array di numeri interi che ha la somma massima. 

È una sfida comune nei corsi di algoritmi e strutture dati, ed è spesso utilizzato per insegnare tecniche di programmazione dinamica.

Descrizione del problema

Dato un array di numeri interi, dobbiamo identificare il sottoarray contiguo che ha la somma più alta. Ad esempio, dato l'array {-2, 1, -3, 4, -1, 2, 1, -5, 4}, il sottoarray di somma massima è {4, -1, 2, 1}, con una somma di 6.

Soluzione con Algoritmo di Kadane

L'algoritmo di Kadane risolve questo problema in tempo lineare, O(n), rendendolo molto efficiente. L'idea principale è iterare attraverso l'array mantenendo la somma massima trovata finora e la somma corrente del sottoarray che stiamo considerando. Se la somma corrente diventa negativa, la resettiamo a zero perché qualsiasi sottoarray futuro conterrà necessariamente un numero maggiore.

Pseudocodice di Kadane

  1. Inizializzare due variabili: max_so_far e max_ending_here.

  2. Iterare attraverso l'array:

    1. Aggiornare max_ending_here aggiungendo l'elemento corrente dell'array.

    2. Se max_ending_here è maggiore di max_so_far, aggiornare max_so_far.

    3. Se max_ending_here è minore di zero, resettiamo max_ending_here a zero.

Implementazione in C

Ecco un'implementazione dettagliata dell'algoritmo di Kadane in C:

#include <stdio.h> // Funzione per trovare il sottoarray di somma massima int maxSubArraySum(int arr[], int size) { int max_so_far = arr[0]; int max_ending_here = arr[0]; for (int i = 1; i < size; i++) { // Includi l'elemento corrente nel sottoarray corrente if (max_ending_here < 0) { max_ending_here = arr[i]; } else { max_ending_here += arr[i]; } // Aggiorna la somma massima finora se necessario if (max_ending_here > max_so_far) { max_so_far = max_ending_here; } } return max_so_far; } int main() { int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; int n = sizeof(arr) / sizeof(arr[0]); int max_sum = maxSubArraySum(arr, n); printf("La somma massima del sottoarray è %d\n", max_sum); return 0; }

Analisi del codice

Inizializzazione:

int max_so_far = arr[0]; int max_ending_here = arr[0];

Inizializziamo entrambe le variabili al primo elemento dell'array. max_so_far tiene traccia della somma massima trovata finora, mentre max_ending_here tiene traccia della somma del sottoarray corrente.

Iterazione:

for (int i = 1; i < size; i++) {     if (max_ending_here < 0) {         max_ending_here = arr[i];     } else {         max_ending_here += arr[i];     }     if (max_ending_here > max_so_far) {         max_so_far = max_ending_here;     } }

Per ogni elemento dell'array, aggiorniamo max_ending_here aggiungendo l'elemento corrente. Se max_ending_here diventa negativo, lo resettiamo al valore dell'elemento corrente. Aggiorniamo max_so_far se max_ending_here è maggiore.


Risultato:

return max_so_far;

Al termine dell'iterazione, max_so_far conterrà la somma massima del sottoarray.

Variazioni e ottimizzazioni

L'algoritmo di Kadane è ottimale per questo problema in termini di complessità temporale. Tuttavia, ci sono alcune variazioni e ottimizzazioni che possono essere considerate in base alle esigenze specifiche:

  • Indici del sottoarray: Se è necessario anche trovare gli indici del sottoarray di somma massima, possiamo mantenere traccia degli indici di inizio e fine del sottoarray corrente e aggiornare questi indici quando troviamo una nuova somma massima.

  • Input negativi: Se l'array contiene solo numeri negativi, Kadane troverà comunque la soluzione corretta, ma potrebbe essere necessario gestire esplicitamente questo caso in alcune applicazioni.

Conclusione

Trovare il sottoarray di somma massima è un problema essenziale in informatica che può essere risolto in modo efficiente utilizzando l'algoritmo di Kadane. La comprensione di questo algoritmo e della sua implementazione in C è una parte fondamentale della formazione in algoritmi e programmazione dinamica.

Indice pagine linguaggio C: