HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > Алгоритмы и структуры данных — 2020. Набор задач 3 > problem:


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

Алгоритмы и структуры данных — 2020. Набор задач 3

Start: Oct.02.2020 at 08:00:00 AM
Finish: Oct.16.2021 at 08:00:00 AM
The contest is finished!
• Contest scoreboard

Contest problems

• Подсказки к задачам
• A. Непрерывный рюкзак
• B. Жадина
• C. Количество путей
• D. ЕГЭ — B1
• E. Ежевика
• F. Демоническое программирование
• G. Подотрезок с максимальной ...
• H. Наибольшая возрастающая под...

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