Segmento di somma massima Dato un vettore di interi, sia postivi che negativi, v[0..n-1], definiamo: j S (v[i.. j ]) = ∑ v[k ] = v[i ] + L + v[ j ] con 0 ≤ i ≤ j < n. k =i Si vuole calcolare il massimo delle somme S (v[i.. j ]). Esercizio 1. Si implementi dapprima la funzione: int SommaSeg(int v[], int i, int j) // pre: 0 <= i <= j < dimensione di v[] // post: ritorna S(v[i..j]) per il calcolo di S (v[i.. j ]) , quindi si realizzi una prima versione della funzione: int MaxSommaVett(int v[], int n, int& a, int& b) // pre: 0 <= n <= dimensione di v[] // post: restituisce il massimo valore di S(v[i..j]) // assegnando a = i, b = j generando tutti i possibili segmenti [i..j] con i ≤ j di v[0..n-1] e calcolandone ogni volta la somma per trovare e restituire il massimo. Qual è la complessità temporale di questo algoritmo? Esercizio 2. Sulla base della considerazione che: S (v[i.. j + 1]) = S (v[i.. j ]) + v[ j + 1] si modifichi il programma precedente in modo che, anziché utilizzare SommaSeg(), la somma venga accumulata su una variabile di MaxSommaVett(). La soluzione dovrebbe avere complessità O(n 2 ) . Esercizio 3. Sia v[i..j] un segmento di lunghezza minima e somma massima; allora: a) S (v[i..k ]) > 0 per ogni i ≤ k < j . Se così non fosse, si avrebbe che S (v[i.. j ]) ≤ S (v[k + 1.. j ]) contro l’ipotesi di lunghezza minima; b) S (v[k ..i − 1]) ≤ 0 per ogni 0 ≤ k < i . Altrimenti per qualche k ∈ [0..i − 1] avremmo che S (v[i.. j ]) < S (v[k .. j ]) , contro la massimalità della somma S (v[i.. j ]) . Ne segue che, nella scansione di v[], quando la somma diventa negativa o nulla, basta considerare un nuovo segmento successivo e disgiunto da quelli considerati precedentemente. Sulla base di queste osservazioni, si implementi una terza versione dello stesso programma, la quale abbia complessità O(n). È quest’ultima asintoticamente ottima? Giustificare la risposta.