teddy online judge

69. Regalos

Limite de tiempo : 1 seg.   Total runs : 68  Aceptados : 17

El día de hoy es el cumpleaños de Juan y sus amigos y familiares le han entregado varios presentes. Como Juan eres una persona muy caritativa, no te quedarás con todos los regalos y algunos los donarás a varias instituciones educativas. Los regalos han sido colocados en una sola fila y Juan ha calificado cada regalo en un rango entre -100 y 100, donde 100 significa que le gusta mucho y -100 significa que preferiría donarlo. Sus padres le han dicho que deben seleccionar una serie de regalos consecutivos, para que los asistentes a la fiesta no se sientan mal porque Juan no haya escogido su regalo. Sin embargo, Juan quiere escoger la serie de regalos consecutivos que más le agraden, es decir, cuya suma de calificaciones se máxima. Para darse una idea, Juan ha pedido tu ayuda para calcular cuál es la suma máxima de calificación que podría obtener.

Problema
Escribe un programa que dada la cantidad de regalos y las calificaciones de cada uno de ellos, regrese la suma del intervalo que maximiza la suma de calificaciones.

Entrada
La primer línea de la entrada tendrá un número P que indica el numero de casos de prueba, la primer línea de cada caso de prueba tendrá 1<=n<=10000 que representa la cantidad de regalos que Juan tiene. La siguiente línea contendrá n números -100<=Xi<=100 que representan la calificación de cada uno de los regalos.

Salida
Un solo número que representa la suma del intervalo con máxima suma.

Ejemplo

Entrada

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

Salida

6
9

Autor: Joemmanuel Ponce Galindo, ITESM Campus León