Дан список произвольных целых чисел. Напишите программу, которая находит непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие
i и
j (
i<=j), что сумма всех элементов массива от
ai до
aj включительно будет максимальна.
Индексация элементов начинается с 1.
Входные данные
В первой строке задается натуральное число
n — количество элементов в списке.
В следующих строках задаются сами элементы списка — целые числа.
Выходные данные
Выведите пару искомых значений индексов. Если таких пар несколько, то
j должно быть минимально возможным, а при равных
j значение
i должно быть максимально возможным.
В первой строке выведите
i, во второй -
j.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
-1
2
3
-2
2 |
2
3 |
| 2 |
7
2
-2
3
-1
5
-2
7 |
3
7 |
Пояснение
При решении задания нельзя использовать массивы для хранения данных
Запрещенные операторы: [; ]