Задача №1584. Отрезок с максимальной суммой
В одномерном массиве, заполненном произвольными целыми числами, за один проход найдите непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие \(i\) и \(j\) (\(i \le j\)), что сумма всех элементов массива от \(a_i\) до \(a_j\) включительно будет максимальна.
Входные данные
На вход программе сначала подается натуральное \(n \le 100 000\) — количество элементов в массиве. Далее, по одному в строке расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000.
Выходные данные
Выдайте пару искомых значений индексов. Если таких пар несколько, то \(j\) должно быть минимально возможным, а при равных \(j\) значение \(i\) должно быть максимально возможным.
Примеры
Входные данные
5 -1 2 3 -2 2
Выходные данные
2 3
Входные данные
7 2 -2 3 -1 5 -2 7
Выходные данные
3 7
Сдать: для сдачи задач необходимо войти в систему