ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Сборник > задача:


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

Задачи сборника

• Периметр треугольника
• Площадь выпуклого четурёхуголь...
• Площадь и периметр
• Площадь круга
• Площадь треугольника
• Площадь треугольника (по длинам...
• Площадь треугольника (по точкам)
• Побочная диагональ
• Подотрезок с максимальной с...
• Подстрока: от i до j
• Подстрока: от i до j по k
• Позиция буквы
• Позиция буквы 2
• Покупка канцелярии
• Покупка линолеума
• Покупка пирожков
• Полосатый флаг

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Подотрезок с максимальной суммой
Подотрезок с максимальной суммой
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив A, элементами которого являются целые числа.

Найдите в нём непрерывную последовательность элементов, сумма которых является максимальной.

Входные данные

Первая строка содержит целое число N (1 ≤ N ≤ 104) — количество элементов массива.

Вторая строка содержит N целых чисел Ai ( - 104 ≤ Ai ≤ 104) — элементы массива.

Выходные данные

Выведите два целых числа L и R (0 ≤ L ≤ R ≤ N - 1) — соответственно начальный и конечный индексы подотрезка с максимальной суммой.

Если возможных ответов несколько, выведите тот, в котором L минимально. Если возможных ответов всё ещё несколько, выведите тот, в котором R минимально.

Примеры

Входные данные
8
-8 5 -2 7 4 -15 3 4
Выходные данные
1 4
Входные данные
5
2 1 -5 0 3
Выходные данные
0 1
Входные данные
8
7 -9 -5 5 -6 4 -2 10
Выходные данные
5 7
Для отправки решений необходимо выполнить вход.

www.contester.ru