Задача

2 /9


Отрезок с максимальной суммой

Теория Нажмите, чтобы прочитать/скрыть


Задача

В одномерном массиве, заполненном произвольными целыми числами, за один проход найдите непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие i и j (i≤j), что сумма всех элементов массива от ai до aj включительно будет максимальна.

Входные данные
На вход программе сначала подается натуральное ≤100000 — количество элементов в массиве. Далее, по одному в строке расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000.

Выходные данные
Выдайте пару искомых значений индексов. Если таких пар несколько, то j должно быть минимально возможным, а при равных j значение i должно быть максимально возможным.
Примеры
входные данные выходные данные
5
-1
2
3
-2
2
2
3
7
2
-2
3
-1
5
-2
7
3
7

time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6410
Python195
PascalABC7
Комментарий учителя