Problem
Étant donné un tableau d'entiers arbitraires. Écrivez un programme qui, en un passage dans le tableau, trouve une pièce continue dont la somme des nombres est maximale.
Note. En fait, il est nécessaire de trouver
i et
j (
i<=j) tels que la somme de tous les éléments du tableau de
ai< /sub> jusqu'à
aj inclus sera le maximum.
Entrée
La première ligne est un nombre naturel
n <= 100000 — le nombre d'éléments dans le tableau. Les lignes
n suivantes définissent les éléments réels du — entiers, modulo n'excédant pas 30 000.
Mentions légales
Générez une paire de valeurs d'index souhaitées. S'il y a plusieurs paires de ce type, alors
j doit être le minimum possible, et si
j sont égaux, la valeur de
i doit être le maximum possible. Sur la première ligne, écrivez
i, sur la seconde -
j.
Exemples
| # |
Entrée |
Sortie |
| 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