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
-2 1 -3 4 -1 3 1 -4 -2 | 7 |
10
1 -2 3 4 -3 1 7 -10 -20 4 | 12 |
Explicación
- -2 1 -3
4 -1 3 1-4 -2 → La suma del subarreglo resaltado es (4 - 1 + 3 + 1) = 7
- 1 -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: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB