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

Разделы > 103. Динамическое программирование > задача:


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

Задачи раздела

• Игра с разрезанием
• Количество путей
• Макс и Дом интернета
• Макс и бельевая верёвка
• Наибольшая возрастающая подпос...
• Наибольшая общая подпоследова...
• Непрерывный рюкзак
• Несчастливые дни
• Подотрезок с максимальной с...
• Распределение студентов
• Странная функция
• Экзаменационные билеты
• Экспериментальный отбор

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

Если у вас есть предложения или пожелания по работе 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