Problem
Dado um array de números inteiros arbitrários. Escreva um programa que em uma passagem pelo array encontre uma peça contínua, cuja soma dos números seja máxima.
Observação. Na verdade, é necessário encontrar
i e
j (
i<=j) de forma que a soma de todos os elementos da matriz de
ai até e incluindo
aj será o máximo.
Entrada
A primeira linha é um número natural
n <= 100000 — o número de elementos na matriz. As seguintes linhas
n definem os elementos reais do — inteiros, módulo não superior a 30.000.
Impressão
Emita um par de valores de índice desejados. Se houver vários desses pares,
j deve ser o mínimo possível e, se
j forem iguais, o valor de
i deve ser o máximo possível. Na primeira linha imprima
i, na segunda -
j.
Exemplos
| # |
Entrada |
Saída |
| 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