Il problema massimo del sottoarray è lo stesso del problema della sezione massima. Questo tutorial discute il problema con la codifica in C++. La domanda è: qual è la somma massima di qualsiasi possibile sequenza di numeri consecutivi all'interno di un array? Questo può significare l'intero array. Questo problema e la sua soluzione in qualsiasi lingua sono indicati come il problema massimo del sottoarray. L'array può avere possibili numeri negativi.
La soluzione deve essere efficiente. Deve avere la complessità del tempo più veloce. A partire da ora, l'algoritmo più veloce per la soluzione è noto nella comunità scientifica come l'algoritmo di Kadane. Questo articolo spiega l'algoritmo di Kadane con C++.
Esempi di dati
Considera il seguente vettore (array):
vettore < int > A = { 5 , - 7 , 3 , 5 , - Due , 4 , - 1 } ;
La fetta (sottoarray) con la somma massima è la sequenza {3, 5, -2, 4}, che dà una somma di 10. Nessun'altra sequenza possibile, nemmeno l'intero array, darà una somma fino a il valore di 10. L'intero array fornisce una somma di 7, che non è la somma massima.
Considera il seguente vettore:
vettore < int > B = { - Due , 1 , - 3 , 4 , - 1 , Due , 1 , - 5 , 4 } ;
La fetta (sottomatrice) con la somma massima è la sequenza {4, −1, 2, 1} che dà una somma di 6. Si noti che possono esserci numeri negativi all'interno della sottomatrice per la somma massima.
Considera il seguente vettore:
vettore < int > C = { 3 , Due , - 6 , 4 , 0 } ;
La fetta (sub-array) con la somma massima è la sequenza {3, 2} che dà una somma di 5.
Considera il seguente vettore:
vettore < int > D = { 3 , Due , 6 , - 1 , 4 , 5 , - 1 , Due } ;
Il sottoarray con la somma massima è la sequenza {3, 2, 6, -1, 4, 5, -1, 2} che dà una somma di 20. È l'intero array.
Considera il seguente vettore:
vettore < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , quindici , 4 , - 8 , - quindici , - 22 } ;
Ci sono due sotto-array con somme massime, qui. La somma più alta è quella che viene considerata come soluzione (risposta) per il problema del sottoarray massimo. I sottoarray sono: {5, 7} con una somma di 12, e {6, 5, 10, -5, 15, 4} con una somma di 35. Naturalmente, la slice con la somma di 35, è la risposta.
Considera il seguente vettore:
vettore < int > F = { - 4 , 10 , quindici , 9 , - 5 , - venti , - 3 , - 12 , - 3 , 4 , 6 , 3 , Due , 8 , 3 , - 5 , - Due } ;
Ci sono due sottoarray con somme massime. La somma maggiore è quella che viene considerata come soluzione per il problema di massimo sottoarray. I sottoarray sono: {10, 15, 9} con una somma di 34 e {4, 6, 3, 2, 8, 3} con una somma di 26. Naturalmente, la slice con la somma di 34 è la risposta perché il problema è cercare il sottoarray con la somma più alta e non il sottoarray con la somma più alta.
Sviluppo dell'algoritmo di Kadane
Le informazioni in questa sezione del tutorial non sono il lavoro originale di Kadane. È il modo in cui l'autore insegna l'algoritmo di Kadane. Uno dei vettori di cui sopra, con i suoi totali parziali, è in questa tabella:
| Dati | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | quindici | 4 | -8 | -quindici | -22 |
| Totale parziale | 5 | 12 | 8 | -Due | -8 | -Due | 3 | 13 | 8 | 23 | 27 | ventuno | 16 | -6 |
| indice | 0 | 1 | Due | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | undici | 12 | 13 |
Il totale parziale per un indice è la somma di tutti i valori precedenti, incluso quello per l'indice. Ci sono due sequenze con somme massime qui. Sono {5, 7}, che dà una somma di 12, e {6, 5, 10, -5, 15, 4}, che dà una somma di 35. La sequenza che dà una somma di 35 è quella desiderata .
Nota che per i totali parziali, ci sono due picchi che sono i valori, 12 e 27. Questi picchi corrispondono agli ultimi indici delle due sequenze.
Quindi, l'idea dell'algoritmo di Kadane è di fare il totale parziale confrontando le somme massime man mano che vengono incontrate, spostandosi da sinistra a destra nella matrice data.
Un altro vettore dall'alto, con i suoi totali parziali, è in questa tabella:
Ci sono due sequenze con somme massime. Sono {10, 15, 9}, che dà una somma di 34; e {4, 6, 3, 2, 8, 3} che dà una somma di 26. La sequenza che dà la somma di 34, è quella desiderata.
Si noti che per i totali parziali ci sono due picchi che sono i valori, 30 e 13. Questi picchi corrispondono agli ultimi indici delle due sequenze.
Ancora una volta, l'idea dell'algoritmo di Kadane è di fare il totale parziale confrontando le somme massime man mano che vengono incontrate, spostandosi da sinistra a destra nella matrice data.
Codice dell'algoritmo di Kadane in C++
Il codice fornito in questa sezione dell'articolo non è necessariamente quello utilizzato da Kadane. Tuttavia, è dal suo algoritmo. Il programma, come molti altri programmi C++, inizierebbe con:
#includi#includi
usando lo spazio dei nomi std;
C'è l'inclusione della libreria iostream, che è responsabile dell'input e dell'output. Viene utilizzato lo spazio dei nomi standard.
L'idea dell'algoritmo di Kadane è di avere il totale parziale confrontando le somme massime man mano che vengono incontrate, spostandosi da sinistra a destra nell'array dato. La funzione per l'algoritmo è:
int maxSunArray ( vettore < int > & UN ) {int N = A.taglia ( ) ;
int somma massima = A [ 0 ] ;
int runTotale = A [ 0 ] ;
per ( int io = 1 ; io < N; io++ ) {
int tempRunTotal = runTotal + A [ io ] ; // potrebbe essere più piccolo di A [ io ]
Se ( UN [ io ] > tempRunTotale )
runTotale = A [ io ] ; // in Astuccio UN [ io ] è maggiore del totale parziale
altro
runTotal = tempRunTotal;
Se ( runTotale > importo massimo ) // confrontando tutte le somme massime
maxSum = runTotal;
}
Restituzione importo massimo;
}
Viene determinata la dimensione, N della matrice data (vettore). La variabile maxSum è una delle possibili somme massime. Un array ha almeno una somma massima. La variabile runTotal rappresenta il totale parziale di ciascun indice. Vengono inizializzati entrambi con il primo valore dell'array. In questo algoritmo, se il valore successivo nell'array è maggiore del totale parziale, il valore successivo diventerà il nuovo totale parziale.
C'è un ciclo for principale. La scansione inizia da 1 e non da zero a causa dell'inizializzazione delle variabili, maxSum e runTotal su A[0] che è il primo elemento dell'array dato.
Nel ciclo for, la prima istruzione determina un totale parziale temporaneo aggiungendo il valore corrente alla somma accumulata di tutti i valori precedenti.
Successivamente, c'è un costrutto if/else. Se il valore corrente da solo è maggiore del totale parziale fino a quel momento, quel singolo valore diventa il totale parziale. Questo è utile soprattutto se tutti i valori nella matrice data sono negativi. In questo caso, il valore negativo più alto da solo diventerà il valore massimo (la risposta). Se il valore corrente da solo non è maggiore del totale parziale temporaneo finora, il totale parziale diventa il totale parziale precedente più il valore corrente, – questa la parte else del costrutto if/else.
L'ultimo segmento di codice nel ciclo for sceglie tra qualsiasi somma massima precedente per una sequenza precedente (sottoarray) e qualsiasi somma massima corrente per una sequenza corrente. Si sceglie quindi il valore più alto. Può esserci più di una somma massima di sottoarray. Si noti che il totale parziale aumenterebbe e diminuirebbe, poiché l'array viene scansionato da sinistra a destra. Cade quando incontra valori negativi.
La somma massima del sottoarray finale scelta viene restituita dopo il ciclo for.
Il contenuto di una funzione principale C++ adatta, per la funzione dell'algoritmo di Kadane è:
vettore < int > A = { 5 , - 7 , 3 , 5 , - Due , 4 , - 1 } ; // { 3 , 5 , - Due , 4 } - > 10int ret1 = maxSunArray ( UN ) ;
cout << ret1 << fine;
vettore < int > B = { - Due , 1 , - 3 , 4 , - 1 , Due , 1 , - 5 , 4 } ; // { 4 , - 1 , Due , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << fine;
vettore < int > C = { 3 , Due , - 6 , 4 , 0 } ; // { 3 , Due } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << fine;
vettore < int > D = { 3 , Due , 6 , - 1 , 4 , 5 , - 1 , Due } ; // { 3 , Due , 6 , - 1 , 4 , 5 , - 1 , Due } - > 5
int ret4 = maxSunArray ( D ) ;
cout << netto4 << fine;
vettore < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , quindici , 4 , - 8 , - quindici , - 22 } ; // { 6 , 5 , 10 , - 5 , quindici , 4 } - > 35
int ret5 = maxSunArray ( E ) ;
cout << ret5 << fine;
vettore < int > F = { - 4 , 10 , quindici , 9 , - 5 , - venti , - 3 , - 12 , - 3 , 4 , 6 , 3 , Due , 8 , 3 , - 5 , - Due } ; // { 10 , quindici , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << giusto 6 << fine;
Con ciò, l'output sarà:
10
6
5
venti
35
3. 4
Ogni risposta di riga qui, corrisponde a un dato array, in ordine.
Conclusione
La complessità temporale per l'algoritmo di Kadane è O(n), dove n è il numero di elementi nella matrice data. Questa complessità temporale è la più veloce per il problema del sottoarray massimo. Ci sono altri algoritmi che sono più lenti. L'idea dell'algoritmo di Kadane è di fare il totale parziale, confrontando le somme massime man mano che vengono incontrate, spostandosi da sinistra a destra nell'array dato. Se il valore corrente da solo è maggiore del totale parziale fino a quel momento, quel singolo valore diventa il nuovo totale parziale. In caso contrario, il nuovo totale parziale è il totale parziale precedente più l'elemento corrente, come anticipato, durante la scansione dell'array specificato.
Può esserci più di una somma massima, per diversi possibili sottoarray. Viene scelta la somma massima più alta, per tutti i possibili sottoarray.
Quali sono gli indici limite per l'intervallo della somma massima scelta? – Questa è discussione per un'altra volta!
Cris