Отправлено: 15.01.21 09:21. Заголовок: 18. Задачи на последовательность.

День добрый!
Задачи на последовательность вещественных чисел. Возник вопрос:
Если по условию задачи в файле только положительные числа, проблем нет - стандартный алгоритм нахождения максимальной (минимальной) суммы подпоследовательности.
Если по условию задачи в файле как положительные так и отрицательные числа - обработка таких последовательностей для нахождения, например, максимальной суммы становится проблемой.
Например, интересует подпоследовательность, в которой разница между соседними элементами не менее 10. Найти максимальную сумму.
1) 10 20 30 40 - проблем нет, стандартный алгоритм работает,
2) -10 -20 -30 - 40 - проблем нет, стандартный алгоритм,
3) -100 -50 10 20 30 -10 -20 10 40 - 10 - 20 - в таких последовательностях возникает проблема - вначале последовательности идут отрицательные числа. Максимально возможная сумма - 80 (10 20 30 -10 -20 10 40). НО, отрицательные числа, стоящие в начале последовательности, не позволят нам получить этот результат. значит нам надо сохранять всю найденную последовательность и потом ее обрабатывать отдельно, а это уже совсем другая сложность задачи.

 Отправлено: 13.02.21 18:09. Заголовок: nkuznetsov97 пишет: ..

nkuznetsov97 пишет:

цитата:

Логично, что алгоритм, предложенный выше, это не учитывает и поломать его - дело нехитрое. Он нам посчитает какую-то ерунду, посчитает явно сумму от -6 5 15 25.

Попробуйте это доказать. Кстати, и проверить ведь можно.