Для заданного целочисленного массива найдите максимальную сумму подпоследовательности, в которой подпоследовательность не содержит элементов в соседних позициях.
Пример:
Example 1 arr=[4, 1, 1, 4, 2, 1] answer = 9 => arr[0] + arr[3] + arr[5] Example 2 arr=[10, -1, -2, -3, 2] answer = 12 => a[0] + a[4]
- Пройдя несколько примеров, мы понимаем, что нам может понадобиться пропустить более 1 элемента, посмотрите на пример 2.
- Также для каждого элемента нам нужно решить, включать ли его в решение или исключить.
- Давайте применим подход подзадачи.
- Если мы уже знаем решения до индекса i, с этим мы можем найти решение для индекса (i+1)?
- Какая информация нам нужна до индекса i. maxSum до i и и максимальная сумма до i-1.
Recurrence relation f(i) = MAX(arr[i], arr[i] + f(i-2), f(i-1))
- Чтобы сэкономить место, мы можем поддерживать только предыдущие и предыдущие максимальные значения.
Выполнение
Спасибо за прочтение
Удачного кодирования!!!