II Copa MATCOM ACM-ICPCEnded |
A - Intervalo de Suma Máxima
Languages: C, C++, Java, JavaScript, Tiger, Python, Haskell, Pascal, C#
Time & Memory limits: (details)
Dada una lista de $N$ enteros $\{x_1, x_2, \dotsc, x_N\}$ y un conjunto de $Q$ preguntas definidas como $[a, b]$ usted debe calcular el intervalo de suma máxima que está completamente contenido en $[a, b]$. En otras palabras, dado dos enteros $a$ y $b$ $(1 \le a \le b \le N)$ usted debe buscar el intervalo $[i, j]$ tal que $a \le i \le j \le b$ y maximice $x_{i} + x_{i+1} + \dotsb + x_{j}$.
Input
Línea 1
: Un único entero $N$ $(1 \le N \le200000)$.
Línea 2 : $N$ enteros separados por espacio $x_1, x_2, \dotsc, x_N$ $(|xi| ≤ 10000)$.
Línea 3 : Un único entero $Q$ $(1 \le Q \le200000)$.
Línea 4… Q + 3 : Dos enteros $a$ y $b$ $(1 \le a \le b \le N)$ por línea.
Línea 2 : $N$ enteros separados por espacio $x_1, x_2, \dotsc, x_N$ $(|xi| ≤ 10000)$.
Línea 3 : Un único entero $Q$ $(1 \le Q \le200000)$.
Línea 4… Q + 3 : Dos enteros $a$ y $b$ $(1 \le a \le b \le N)$ por línea.
Output
Línea 1…Q
: Por cada pregunta imprima el valor del intervalo de suma máxima contenido completamente en $[a, b]$.
Sample test(s)
Input
10
4 -2 -1 5 -1 0 10 -9 8 -3
5
1 1
2 2
1 10
3 5
4 9
Output
4
-2
15
5
14
Notes
Considere el caso en el ejemplo:
|
Pregunta |
Intervalo De Suma Máxima |
Suma |
|
1 1 |
1 1 |
4 |
|
2 2 |
2 2 |
-2 |
|
1 10 |
1 7 |
4+(-2)+(-1)+5+(-1)+0+10 = 15 |
|
3 5 |
4 4 |
5 |
|
4 9 |
4 7 |
5+(-1)+0+10=14 |