Maior soma em sub-array
#35
Made by: Crazynds
400MB
0.8s
Será dado um array de $N$ elementos contendo valores positivos e negativos. A partir desse array é possivel conseguir diversos sub-arrays continuos como demonstrado abaixo:
Sua tarefa será descobrir a maior soma que é possivel fazer entre todos os sub-arrays.
Input
Será dado na primeira linha um $N$ representando a quantidade de elementos no array. $(1\le N \le 10^7)$
Na próxima linha serão dados $N$ valores $a_i$ de cada elemento no array. $(-10^6 \le a_i \le 10^6)$
Output
Deverá ser dado como saida a maior soma de sub-arrays contínuo que é possivel conseguir entre todos os sub-arrays.
Input Example
Output Example
10 3 1 -8 5 -3 -5 4 -1 -2 6
7
16 13 -10 3 -8 6 6 -3 4 3 -5 8 -7 3 -7 -3 10
19