Алгоритм нахождения максимальной подпоследовательности массива положительных чисел. Поймать: не допускаются смежные элементы

Question

Например, учитывая

A = [1,51,3,1,100,199,3], maxSum = 51 + 1 + 199 = 251.

ясно max(oddIndexSum,evenIndexSum) работает не работает.

Основная проблема, с которой я столкнулся, заключается в том, что я не могу придумать критерий выбора элемента. Критерий отклонения тривиален с учетом критерия выбора.

Стандартный алгоритм максимальной подпоследовательности здесь не применим. Я попробовал подход динамического программирования, но не могу придумать это также. Единственный подход, который я мог придумать, - это использование генетического алгоритма.

Как бы вы подошли к этому?

Answer 1

while you still have elements
     find the largest element, add it to the sum
     remove the element before and after the current

Answer 2

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

Кроме этого случая вы ищете самый дорогой маршрут через (плотный) график? В этом случае вершины - это просто сами числа, ребра не направлены и не имеют веса, и все вершины связаны, кроме вершин, которые были смежны с ними в исходном списке?

Answer 3

max (oddIndexSum, evenIndexSum) не работает

Для примера, который вы привели, он есть - однако, если у вас есть что-то вроде: A = [1, 51, 3, 2, 41, 23, 20], вы можете иметь 51 + 2 + 23 = 76 или 51 + 41 + 20 = 112, который явно больше и также избегает смежных элементов. Это то, что вы ищете?