Для заданного целочисленного массива найдите максимальную сумму подпоследовательности, в которой подпоследовательность не содержит элементов в соседних позициях.

Пример:

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))
  • Чтобы сэкономить место, мы можем поддерживать только предыдущие и предыдущие максимальные значения.

Выполнение

Спасибо за прочтение

Удачного кодирования!!!