Dado un arreglo de n enteros (que pueden ser negativos), encuentra la suma máxima que puede tener un subarreglo contiguo no vacío.

Entrada: Primera línea: n. Segunda línea: n enteros separados por espacio.

Salida: Un entero: la suma máxima del subarreglo.

Restricciones: 1 ≤ n ≤ 10^5, -10^4 ≤ a[i] ≤ 10^4

Casos de prueba

• Caso 1

  • Entrada:

    1
    -5
    

  • Salida: -5
  • Explicación: Solo hay un elemento.

• Caso 2

  • Entrada:

    5
    1 2 3 4 5
    

  • Salida: 15
  • Explicación: Todo el arreglo.

• Caso 3

  • Entrada:

    5
    -2 1 -3 4 -1
    

  • Salida: 4
  • Explicación: El subarreglo [4] tiene la suma máxima.

• Caso 4

  • Entrada:

    9
    -2 1 -3 4 -1 2 1 -5 4
    

  • Salida: 6
  • Explicación: El subarreglo [4, -1, 2, 1] tiene suma 6.

• Caso 5

  • Entrada:

    4
    -3 -1 -4 -2
    

  • Salida: -1
  • Explicación: El subarreglo con suma máxima es [-1], que corresponde al menor número negativo.