Условие:
В одномерном массиве, заполненном произвольными целыми числами, за один проход найдите непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие i
и j
(i≤j
), что сумма всех элементов массива от ai
до aj
включительно будет максимальна.
На вход программе сначала подаётся натуральное n≤100000
— количество элементов в массиве. Далее, по одному в строке расположены сами элементы массива — целые числа, по модулю не превосходящие 30000
.
Выдайте пару искомых значений индексов. Если таких пар несколько, то j
должно быть минимально возможным, а при равных j
значение i
должно быть максимально возможным.
