Sottovettore contiguo con somma massima
Data un'array di
n numeri interi, si richiede di trovare un sottovettore contiguo la cui somma sia la più alta possibile.Input
La prima riga di input contiene un intero
n, che indica il numero di elementi nell’array (1 ≤ n ≤ ).La riga successiva contiene
n interi separati da uno spazio, che rappresentano gli elementi dell’array .Output
Il programma deve stampare un singolo valore intero: la somma massima ottenibile da un sottovettore contiguo dell’array.
Esempi
Input | Output |
9
-2 1 -3 4 -1 3 1 -4 -2 | 7 |
10
1 -2 3 4 -3 1 7 -10 -20 4 | 12 |
Spiegazione
- -2 1 -3
4 -1 3 1-4 -2 → La somma del sottovettore evidenziato è (4 - 1 + 3 + 1) = 7
- 1 -2
3 4 -3 1 7-10 -20 4 → La somma del sottovettore in evidenza è 3 + 4 -3 + 1 + 7 = 12
Possiamo renderlo ancora più efficiente 😎?
È possibile risolvere questo problema senza utilizzare ulteriori array. Riusciresti a farlo?
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB