El Challenge de Petr P57129

Topcoder es una web de concursos de programación. Cada SRM (concurso) tiene 3 partes, la primera de las cuales consiste en una hora y cuarto para programar 3 problemas de 250, 500 y 1000 puntos (cada uno más difícil que el anterior). Después de cinco minutos de descanso hay 15 minutos para hacer challenges. Un challenge es un intento encontrar un caso de prueba en que el programa de un competidor falle, después de ver su código. Obtienes 50 puntos por cada challenge exitoso, y pierdes −25 puntos por cada challenge erróneo. En este problema, sin embargo, consideramos que las puntuaciones de los challenges varían entre −100 y +100, ambos inclusive.

Petr es una leyenda de Topcoder. Tiene un problema: es un maníaco de las estadísticas y los porcentajes. Entre otras muchas cosas, necesita conocer su mejor “racha” de challenges de cada SRM. Una “racha” de challenges es una subsecuencia consecutiva de challenges dentro de la secuencia de todos los challenge que ha hecho durante el concurso (el valor de la “racha” es la suma de todos las puntuaciones obtenidas en todos los challenges de la misma). La subsecuencia podría ser de tamaño 0 (Petr podría fallar todos sus challenges: al fin y al cabo, es ruso, no chino), en cuyo caso el resultado sería 0.

¿Eres capaz de hacer un programa que calcule rapidamente la mejor “racha” de un SRM? ¡De este modo, podría hacer tantos challenges en los SRM como quisiera!

Entrada

Una línea con el número N≥ 0 de challenges realizados por Petr, seguido de una secuencia de N enteros entre −100 y 100 con las puntuaciones obtenidas en los mismos.

Salida

Una línea con el valor de la mejor “racha” que sea posible obtener de la secuencia de challenges.

Puntuación

• TestA:  10 Puntos 

  Entradas con todos los challenges de valor no negativo con N<10⁵.

• TestB:   Entradas con N<10².  30 Puntos 

• TestC:   Entradas con N<10⁴.  40 Puntos 

• TestD:   Entradas con N<10⁶.  20 Puntos