Ad esempio, nella seguente sequenza il massimo sottoarray è $S[5\dots 7]$ perchè nessuna altra sottosequenza è maggiore di 15 (somma degli elementi con indice 5, 6 e 7).
Soluzione 1: Brute Force
Complessità: $O(n^3)$
L’idea è quella di esaminare tutti i possibili sottoarray
#include <iostream> using namespace std; void msbf(const int*, const unsigned int, int&, int&, int&); int main(int argc, char **argv) { int int_arr[10] = { 2, -1, 3, -2, -3, 8, 2, 5, -5, 1 }; int low{ -1 }; int high{ -1 }; int maxsum{ 0 }; msbf(int_arr, 10, low, high, maxsum); return 0; } void msbf(const int* pInt, const unsigned int n, int& low_index, int& high_index, int& max) { max = pInt[0]; // i-esimo elemento tiene traccia dell'indice di partenza del massimo sottoarray for (int i = 0; i < n; ++i) { // j-esimo elemento tiene traccia dell'indice finale del massimo sottoarray for (int j = i; j < n; ++j) { int sum{ 0 }; // z-esimo elemento va da i a j (dato che elementi sono contigui) for (int z = i; z <= j; ++z) { sum += pInt[z]; } if (sum > max) { max = sum; low_index = i; high_index = j; cout << "(" << low_index << ", " << high_index << ") = " << max << '\n'; } } } }
Soluzione 2: Ancora Brute Force
Complessità: $O(n^2)$
Osservando bene si nota che il ciclo più interno della funzione msbf ricalcola ad ogni iterazione la somma parziale, ripetendo quindi gli stessi calcoli più volte. Tutto questo può essere evitato sfruttando la banale formula ricorsiva $sum(i,j) = \sum_{x=i}^j A[x] = sum(i, j-1) + A[j]$:
void msbf(const int* pInt, const unsigned int n, int& low_index, int& high_index, int& max) { max = pInt[0]; // i-esimo elemento tiene traccia dell'indice di partenza del massimo sottoarray for (int i = 0; i < n; ++i) { int sum{ 0 }; // j-esimo elemento tiene traccia dell'indice finale del massimo sottoarray for (int j = i; j < n; ++j) { sum += pInt[j]; if (sum > max) { max = sum; low_index = i; high_index = j; cout << "(" << low_index << ", " << high_index << ") = " << max << '\n'; } } } }
Soluzione 3: Ricorsione
Complessità: $O(n\;log(n))$
L’idea è quella di dividere il problema (in questo caso l’array) in parti più piccole fino a quando non si raggiunge una dimensione del problema (array di un solo elemento in questo caso) tale che permetta una soluzione banale e che serva (insieme a tutte le altre soluzioni banali) a risolvere il problema principale. A questo scopo, ad ogni chiamata ricorsiva l’array viene diviso in due parti. Impostando $mid = \frac{N+1}{2}$ ed a quel punto il massimo subarray si trova o sulla parte sinistra $S[0, mid]$, o sulla parte destra $S[mid+1, N-1]$, o a cavallo tra queste due partizioni. Ogni array di quest’ultimo tipo (che passa dalla posizione con indice $mid$) può essere pensato come formato da due sottoarray del tipo $S[i, mid]$ e $S[mid+1,j]$ con $0\le i \le mid < j \le N-1$, quindi basta trovare i massimi sottoarray di questi due tipi e combinarli per avere il massimo sottoarray relativo alla partizione a cavallo della posizione $mid$. Quindi, in conclusione, basta trovare i massimi sottoarray della parte sinistra, della parte destra e della parte a cavallo e scegliere, tra questi ultimi tre, il massimo.
#include <iostream> #include <cmath> using namespace std; struct Maxsubinfo { int low_index{ -1 }; int high_index{ -1 }; int sum{ 0 }; }; Maxsubinfo msrecurs(const int*, const size_t, int, int); int main(int argc, char **argv) { int int_arr[10] = { 2, -1, 3, -2, -3, 8, 2, 5, -5, 1 }; Maxsubinfo msi = msrecurs(int_arr, 10, 0, 9); cout << "(" << msi.low_index << ", " << msi.high_index << ") = " << msi.sum; return 0; } Maxsubinfo ms_middle(const int* pInt, const size_t n, int low_index, int mid_index, int high_index) { Maxsubinfo msi; int left_sum{ -1 }; int sum{ 0 }; for (int i = mid_index; i >= low_index; --i) { sum += pInt[i]; if (sum > left_sum) { left_sum = sum; msi.low_index = i; } } int right_sum{ -1 }; sum = 0; for (int j = mid_index + 1; j <= high_index; ++j) { sum += pInt[j]; if (sum > right_sum) { right_sum = sum; msi.high_index = j; } } msi.sum = left_sum + right_sum; return msi; } Maxsubinfo msrecurs(const int* pInt, const size_t n, int low_index, int high_index) { if (low_index == high_index) // caso base: un solo elemento { Maxsubinfo msi; msi.low_index = low_index; msi.high_index = high_index; msi.sum = pInt[low_index]; return msi; } else { Maxsubinfo msi_left; Maxsubinfo msi_middle; Maxsubinfo msi_right; int mid_index = floor((low_index + high_index) / 2); msi_left = msrecurs(pInt, n, low_index, mid_index); msi_right = msrecurs(pInt, n, (mid_index + 1), high_index); msi_middle = ms_middle(pInt, n, low_index, mid_index, high_index); if (msi_left.sum >= msi_right.sum && msi_left.sum >= msi_middle.sum) return msi_left; else if (msi_right.sum >= msi_left.sum && msi_right.sum >= msi_middle.sum) return msi_right; else return msi_middle; } }
Soluzione 4: Kadane (formula ricorsiva)
Complessità: $O(n)$
Assumendo di avere elementi dell'array non tutti negativi, l'idea è che risolvendo il problema del massimo sottoarray per un array di $(n - 1)$ elementi si può risolvere lo stesso problema, in maniera abbastanza semplice, per un array di $n$ elementi. Indicando infatti con $F(i)$ la somma degli elementi del massimo sottoarray trovato in un array $A$ di $i$ elementi si può facilmente verificare che la formula ricorsiva per trovare $F(i)$ è:
$F(i):= \begin{cases} 0, & \text{if $i = 0$,}\\ max((F(i-1) + A[i]), 0), & \text{if $0 \le i \leq n$.} \end{cases}$
Dato che da $(F(i-1) + A[i])$ potrebbe venir fuori un numero negativo è conveniente assegnare a questo il valore $max((F(i-1) + A[i]), 0)$ (in effetti $F(i)$ rappresenta la somma degli elementi del massimo sottoarray, quindi un numero maggiore o uguale a zero pere un array di elementi non tutti negativi).
#include <iostream> #define max(a,b) (((a) > (b)) ? (a) : (b)) using namespace std; int F_i(const int*, int, int&, int&, int&); int main(int argc, char **argv) { int int_arr[10] = { 2, -1, 3, -2, -3, 8, 2, 5, -5, 1 }; int low{ -1 }; int high{ -1 }; int maxsum{ 0 }; F_i(int_arr, 10, low, high, maxsum); cout << "(" << low << ", " << high << ") = " << maxsum; return 0; } int F_i(const int* pInt, int n, int& low_index, int& high_index, int& maxx) { static unsigned int low = 0; if (n <= 0) return 0; else { // NOTA: non è pInt[n] // perchè pInt è di 10 elementi quindi arriva al max a pInt[9]. pInt[10] disastro! int fi = F_i(pInt, (n - 1), low_index, high_index, maxx) + pInt[n-1]; // Serie di istruzioni if per calcolare gli indici. // Non sono parte della formula ricorsiva F(i). if (fi < 0) low = n; if (fi > maxx) { maxx = fi; low_index = low; high_index = n - 1; } return max(fi, 0); } }
Nessun commento:
Posta un commento