Форум » Динамическое программирование » 18. Задачи на последовательность. » Ответить
18. Задачи на последовательность.
alspay: День добрый! Задачи на последовательность вещественных чисел. Возник вопрос: Если по условию задачи в файле только положительные числа, проблем нет - стандартный алгоритм нахождения максимальной (минимальной) суммы подпоследовательности. Если по условию задачи в файле как положительные так и отрицательные числа - обработка таких последовательностей для нахождения, например, максимальной суммы становится проблемой. Например, интересует подпоследовательность, в которой разница между соседними элементами не менее 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). НО, отрицательные числа, стоящие в начале последовательности, не позволят нам получить этот результат. значит нам надо сохранять всю найденную последовательность и потом ее обрабатывать отдельно, а это уже совсем другая сложность задачи.
Ответов - 16, стр:
1 2 All
Поляков: nkuznetsov97 пишет: Логично, что алгоритм, предложенный выше, это не учитывает и поломать его - дело нехитрое. Он нам посчитает какую-то ерунду, посчитает явно сумму от -6 5 15 25. Попробуйте это доказать. Кстати, и проверить ведь можно.
полная версия страницы