Problem
Dada una matriz de enteros arbitrarios. Escriba un programa que en una sola pasada a través de la matriz encuentre una pieza continua, la suma de los números en la que es máxima.
Nota. De hecho, se requiere encontrar
i y
j (
i<=j) tales que la suma de todos los elementos de la matriz de
ai< /sub> hasta e incluyendo
aj será el máximo.
Entrada
La primera línea es un número natural
n <= 100000 — el número de elementos en la matriz. Las siguientes líneas
n definen los elementos reales del — números enteros, módulo no superior a 30.000.
Impresión
Muestra un par de valores de índice deseados. Si hay varios de estos pares, entonces
j debería ser el mínimo posible, y si
j son iguales, el valor de
i debería ser el máximo posible. En la primera línea escriba
i, en la segunda -
j.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
5
-1
2
3
-2
2 |
2
3 |
| 2 |
7
2
-2
3
-1
5
-2
7 |
3
7 |
Запрещенные операторы: sort; min; max; reverse; count; sum; index