Максимальная сумма непоследовательных элементов (Dynami c Programming)

Question

Учитывая массив положительных целых чисел, какой алгоритм является наиболее эффективным для поиска непоследовательных элементов из этого массива, которые при сложении дают максимальную сумму?

Динамика * Решение для программирования 1021 * - использовать вспомогательный массив maxSum, содержащий максимальную сумму до этого конкретного индекса. Мы начинаем с установки первых двух индексов массива и заполняем остальную часть массива max(array[i]+maxSum[i-2], maxSum[i-1]).

Я понимаю, что мы не можем добавлять соседние элементы, но я изо всех сил пытаюсь понять, как приведенное выше решение учитывает, что предыдущий элемент в maxSum[i] может не быть результатом суммирования с array[i].

Например:

index:  0 1 2  3 4

array:  3 5 -7 8 10

maxSum: 3 5 5  _ 

Мы видим, что maxSum [2] не является результатом суммирования с массивом [2].

Чтобы найти maxSum[3] = max(array[3]+maxSum[1], maxSum[2]), но почему бы нам не рассмотреть maxSum[2] + array[3]? Поскольку maxSum [2] может не состоять из соседнего значения массива [2].

Answer 1

как в приведенном выше решении учитывается, что предыдущий элемент в maxSum [i] может не быть результатом суммирования с массивом [i]?

Просто . Если предыдущий элемент в maxSum [i] не должен быть включен в результат суммирования с массивом [i], мы можем посмотреть maxSum [i - 2]. Мы делаем это явно в

array[i]+maxSum[i-2]

, мы сравниваем это с вариантом исключения массива [i], который равен

maxSum[i-1]

Answer 2

Я предполагаю, что вам нужно объяснение рассуждений, вот оно.

Пусть M [i] будет максимальной суммой, которую мы можем получить, включив первые i элементы массив A (с условием, что никакие два не идут подряд). Есть две возможности:

1. M [i] включает элемент i. В этом случае он не может включать элемент i-1, поэтому M [i] = A [i] + M [i-2]

2. M [i] не включает элемент i. В этом случае M [i] = M [i-1].

Поскольку мы не знаем, действительно ли он включает i или нет, мы вычисляем оба случая и выбираем максимум между два таким образом

M [i] = max (M [i-1], A [i] + M [i-2])

Answer 3

Во-первых, вы можете не понимать процедуру полностью:

• Для каждого индекса i, maxSum представляет max из (сумма путем включения i-го элемента, сумма путем исключения i -й элемент)
• maxSum[3] = max(array[3]+maxSum[1], maxSum[2]), потому что array[3]+maxSum[1] представляет собой сумму, если берется array[3], и maxSum[2], если array[3] исключено.