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.

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

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.

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.

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.

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.