Sottoarray a Somma Massima con l’Algoritmo Divide & Conquer
Data un’array di
n interi, bisogna individuare un sottoarray contiguo che abbia la somma massima utilizzando la tecnica divide & conquer.Input
La prima riga di input contiene un intero
n – il numero di elementi dell’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 intero: la somma massima ottenibile da uno dei sottoarray presenti nell’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 sottoarray evidenziato è (4 - 1 + 3 + 1) = 7
- 1 -2
3 4 -3 1 7-10 -20 4 → 3 + 4 -3 + 1 + 7 = 12
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB