Subarreglo de suma máxima
Dado un arreglo de n enteros, encuentra un subarreglo contiguo que produzca la suma más grande de valores.
Entrada
La primera línea de la entrada contiene un entero n — la cantidad de elementos en el arreglo (1 ≤ n ≤ ).
La siguiente línea contiene n enteros separados por un espacio, que representan los elementos del arreglo .
Salida
El programa debe imprimir un único entero: la suma más alta que pueda obtenerse de un subarreglo dentro del arreglo dado.
Ejemplos
Entrada | Salida |
|---|---|
9 | 7 |
10 | 12 |
Explicación
-2 1 -3
4 -1 3 1-4 -2 → La suma del subarreglo resaltado es (4 - 1 + 3 + 1) = 71 -2
3 4 -3 1 7-10 -20 4 → 3 + 4 -3 + 1 + 7 = 12
¿Puedes hacerlo todavía mejor 😎?
Es posible resolver este problema sin utilizar arreglos adicionales. ¿Puedes lograrlo?
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB