определение максимального веса разреженного индексного набора массива

Question

Рассмотрим, например, A [14,9,13,4,6,12,11,10]. Наборы индексов {1,3,5} или {1,4,6} являются разреженными. {1,2,5} не являются разреженными, поскольку 1,2 смежны.

вес делается на сумму всех разреженного индекса, например w(1,3,5) = 14 + 13 + 6 = 33

Как можно разработать повторения для W (к) для каждого к, 0 < = к = < п пусть W (K) максимальный вес разреженного индекса для префикса A [1..k] of A?

Как написать псевдокод для динамического программирования, который вычисляет W(k) для всех 0 <= k <= n? Спасибо всем.

Answer 1

Предположим, что индекс массива для A основан на 1. W инициализируется как все нули. W можно рассчитать следующим образом:

W [i] = max (W [i-1], W [i-2] + max (0, A [i]));

Если элементы в массиве A всегда больше нуля, max (0, A [i]) не требуется.