HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


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

Section problems

• Перебор перестановок
• Перебор сочетаний
• Перевод между системами счисления
• Пересчёт рейтинга
• Пишущая машинка
• Плеер
• Площадь и периметр
• Площадь треугольника
• Подотрезок с максимальной с...
• Подсказки к задачам
• Подсказки к задачам
• Подсказки к задачам
• Подсказки к задачам
• Подсказки к задачам
• Подсказки к задачам
• Подсказки к задачам
• Поиск элемента

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 65536/65536/65536/65536 Kb.

Подотрезок с максимальной суммой
Подотрезок с максимальной суммой
ограничение по времени на тест
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