algorithm - 找到数组的稀疏索引集的最大权重

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

如何为每个 k 开发 W(k) 的递归，0 <= k =< n 让 W(k) 成为 A 的前缀 A[1..k] 的稀疏索引集的最大权重？

如何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])。