Эта, на сегодняшний день простая задача была представлена студентам и школьникам для поступления на работу в Яндекс 2011 года, узнайте справились бы вы.
Дан массив целых чисел. Найти отрезок этого массива с максимальной суммой.
Входные данные В первой строке дано натуральное число n ( 1 ≤ n ≤ 10e5 ) — размер массива. Во второй строке через пробел перечислены элемента массива. Числа не превышают 10e4 .
Выходные данные Выведите три числа — индекс начала отрезка, индекс конца и саму максимальную сумму. Массив индексируется с единицы. Если ответов несколько — выведите любой.
5
-1 2 3 -2 5
2 5 8
Можно решить divide & conquer: делим массив пополам. Ответ это либо ответ для правой половины, либо ответ для левой половины, либо максимальный префикс правой половины в сочетании с максимальным суффиксом левой половины. Я прошел? Сложность линейная, так как рекурсивных вызовов будет не больше 4*n. Нужно возвращать макс префикс, его длину, макс суффикс, его длину, и ответ, а потом комбинировать. Можно ДО сверху накатить
Вот задача поинтереснее https://www.e-olymp.com/ru/problems/4498