Problema massimo sotto-array in C ++

Il problema massimo del sotto-array è lo stesso del problema della fetta massima. Questo tutorial discute il problema con la codifica in c++. La domanda è: qual è la somma massima di ogni 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 massimo problema del sotto-array. 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 A = 5, -7, 3, 5, -2, 4, -1;

La fetta (sotto -array) con la somma massima è la sequenza, 3, 5, -2, 4, che dà una somma di 10. Nessun'altra sequenza possibile, anche l'intera array, darà una somma fino al valore di 10. L'intero array dà una somma di 7, che non è la somma massima.

Considera il seguente vettore:

vettore B = -2, 1, -3, 4, -1, 2, 1, -5, 4;

La fetta (sotto-array) 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 del sotto-array per la massima somma.

Considera il seguente vettore:

vettore C = 3, 2, -6, 4, 0;

La fetta (sotto-array) con la somma massima è la sequenza, 3, 2 che dà una somma di 5.

Considera il seguente vettore:

vettore D = 3, 2, 6, -1, 4, 5, -1, 2;

Il sotto -array 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 E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22;

Ci sono due sotto-array con somme massime, qui. La somma più alta è quella che è considerata come soluzione (risposta) per il massimo problema del sotto-array. I sotto -array sono: 5, 7 con una somma di 12 e 6, 5, 10, -5, 15, 4 con una somma di 35. Naturalmente, la fetta con la somma di 35, è la risposta.

Considera il seguente vettore:

vettore F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2;

Ci sono due sotto-array con somme massime. La somma più alta è quella che è considerata una soluzione per il massimo problema del sotto-array. I sotto-array sono: 10, 15, 9 con una somma di 34 e 4, 6, 3, 2, 8, 3 con una somma di 26. Naturalmente, la fetta con la somma di 34 è la risposta perché il problema è cercare il sotto-array con la somma più alta e non il sotto-array con la somma più alta.

Sviluppare l'algoritmo di Kadane

Le informazioni in questa sezione del tutorial non sono l'opera originale di Kadane. È il modo di fare l'autore per insegnare l'algoritmo di Kadane. Uno dei vettori di cui sopra, con i suoi totali in esecuzione, è in questa tabella:

L'esecuzione totale 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 danno 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 è ciò che è desiderato.

Si noti che per i totali in esecuzione, 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 è quella di fare il totale in esecuzione mentre confronta le somme massime quando si incontrano, spostandosi da sinistra a destra nell'array dato.

Un altro vettore dall'alto, con i suoi totali in esecuzione, è 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 è ciò che è desiderato.

Si noti che per i totali in esecuzione, 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 è quella di fare il totale in esecuzione mentre si confronta le somme massime quando si incontrano, spostandosi da sinistra a destra nell'array dato.

Codice dell'algoritmo di Kadane in C++

Il codice indicato in questa sezione dell'articolo non è necessariamente quello che Kadane ha usato. Tuttavia, è dal suo algoritmo. Il programma come molti altri programmi C ++, inizierebbe:

#includere
#includere

Utilizzo dello spazio dei nomi std;

C'è inclusione della libreria iostream, che è responsabile dell'input e dell'output. Viene utilizzato lo spazio dei nomi standard.

L'idea dell'algoritmo di Kadane è quella di avere il totale in esecuzione mentre si confronta le somme massime come si incontrano, spostandosi da sinistra a destra nell'array dato. La funzione per l'algoritmo è:

Int Maxsunarray (Vector &UN)
int n = a.misurare();
int maxsum = a [0];
int runtotal = a [0];
per (int i = 1; i < N; i++)
int tempuntotal = runtotal + a [i]; // potrebbe essere più piccolo di un [i]
if (a [i]> tempuntotal)
runtotal = a [i]; // Nel caso in cui un [i] sia più grande del totale
altro
runtotal = tempuntotal;
if (runtotal> maxsum) // confrontando tutte le somme massime
maxsum = runtotal;

restituire Maxsum;

Viene determinato la dimensione, n dell'array dato (vettore). La variabile, maxsum è una delle possibili somme massime. Un array ha almeno una somma massima. La variabile, runtotal rappresenta il totale in esecuzione su ciascun indice. Sono entrambi inizializzati con il primo valore dell'array. In questo algoritmo, se il valore successivo nell'array è maggiore del totale in esecuzione, quel valore successivo diventerà il nuovo totale in esecuzione.

Ce n'è uno per loop principale. La scansione inizia da 1 e non zero a causa dell'inizializzazione delle variabili, maxsum e runtotal su un [0] che il primo elemento dell'array dato.

Nel loop per loop, la prima istruzione determina un totale di esecuzione temporanea 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 in esecuzione finora, allora quel singolo valore diventa il totale in esecuzione. Questo è utile soprattutto se tutti i valori nell'array dato sono negativi. In questo caso, il solo valore negativo più alto diventerà il valore massimo (la risposta). Se il valore corrente da solo non è maggiore del totale in esecuzione temporanea finora, allora il totale in esecuzione diventa il totale in esecuzione precedente più il valore corrente, - questa parte else del costrutto if/else.

L'ultimo segmento di codice nel per loop prevede tra qualsiasi somma massima precedente per una sequenza precedente (sotto-array) e qualsiasi somma massima corrente per una sequenza corrente. Viene quindi scelto il valore più elevato. Può esserci più di una somma massima sotto-array. Si noti che il totale in esecuzione aumenterebbe e diminuirebbe, poiché l'array viene scansionato da sinistra a destra. Cade mentre soddisfa i valori negativi.

La somma massima del sotto-array prescelta finale viene restituita dopo il loop per loop.

Il contenuto per una funzione principale C ++ adatta, per la funzione dell'algoritmo di Kadane è:

vettore A = 5, -7, 3, 5, -2, 4, -1; // 3, 5, -2, 4 -> 10
int ret1 = maxSunArray (a);
cout << ret1 << endl;
vettore B = -2, 1, -3, 4, -1, 2, 1, -5, 4; // 4, −1, 2, 1 -> 6
int ret2 = maxsunarray (b);
cout << ret2 << endl;
vettore C = 3, 2, -6, 4, 0; // 3, 2 -> 5
int ret3 = maxsunarray (c);
cout << ret3 << endl;
vettore D = 3, 2, 6, -1, 4, 5, -1, 2; // 3, 2, 6, -1, 4, 5, -1, 2 -> 5
int ret4 = maxsunArray (d);
cout << ret4 << endl;
vettore E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22; // 6, 5, 10, -5, 15, 4 -> 35
int ret5 = maxSunArray (E);
cout << ret5 << endl;
vettore F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2; // 10, 15, 9-> 34
int ret6 = maxSunArray (F);
cout << ret6 << endl;

Con ciò, l'output sarà:

10

6

5

20

35

34

Ogni riga risposta qui, corrisponde a un determinato array, in ordine.

Conclusione

La complessità temporale per l'algoritmo di Kadane è O (n), dove n è il numero di elementi nell'array dato. Questa complessità temporale è la più veloce per il massimo problema del sotto-array. Ci sono altri algoritmi che sono più lenti. L'idea dell'algoritmo di Kadane è quella di fare il totale in esecuzione, confrontando le somme massime come si incontrano, spostandosi da sinistra a destra nell'array dato. Se il valore corrente da solo è maggiore del totale in esecuzione finora, allora quel singolo valore diventa il nuovo totale in esecuzione. Altrimenti, il nuovo totale in esecuzione è il totale in esecuzione precedente più l'elemento corrente, come previsto, poiché l'array dato viene scansionato.

Ci può essere più di una somma massima, per diversi possibili sotto-array. Viene scelto la somma massima più alta, per tutti i possibili sotto-array.

Quali sono gli indici limitanti per l'intervallo della somma massima scelta? - Questa è una discussione per qualche altra volta!

Chrys