ЕГЭ: максимальная сумма без соседних элементов
Дана последовательность: 8, 4, 10, 3, 7, 12, 2. Требуется выбрать элементы с максимальной суммой так, чтобы никакие два выбранных элемента не стояли рядом.
Подсказка
Пусть dp[i] — максимальная сумма для первых i элементов. Тогда dp[i]=max(dp[i−1], dp[i−2]+a[i]).
Показать решение
Последовательно: для 8 →8; для 8,4 →8; добавляем 10: max(8,8+10)=18; 3: max(18,8+3)=18; 7: max(18,18+7)=25; 12: max(25,18+12)=30; 2: max(30,25+2)=30. Максимум 30, например 8+10+12.
Показать ответ
30.