Task
Time limit:
1000 ms,
Memory limit:
256 Mb
В одномерном массиве, заполненном произвольными целыми числами, за один проход найдите непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие i и j (i<=j), что сумма всех элементов массива от a
i до a
j включительно будет максимальна.
Входные данные
На вход программе сначала подается натуральное n <= 100000 — количество элементов в массиве. Далее, по одному в строке расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000.
Выходные данные
Выдайте пару искомых значений индексов. Если таких пар несколько, то j должно быть минимально возможным, а при равных j значение i должно быть максимально возможным.
| Ввод |
Вывод |
5
-1
2
3
-2
2 |
2
3 |
7
2
-2
3
-1
5
-2
7 |
3
7 |
Prohibited statements:sort;min;max;reverse;count;sum;index