找到数组中可能的最大总和的最佳答案是什么？

Question

问题是 :

通过选择元素来找到正整数数组中可能的最大总和,使得没有两个元素彼此相邻.

有一个这样的答案:但这个问题的最佳答案是什么

让我们用"t"表示数组并从0开始索引.设f是一个函数,使得f(k)= [0..k]子阵列中的最大和与问题的条件.现在使用动态编程:

f(0) = t[0]
f(1) = max{ t[0], t[1] }
f(k) = max{ f(k-2) + t[k], f(k-1) } if k >= 2

If the array has n elements we need f(n-1).

提前致谢.

Answer 1

您提出的解决方案是一个很好的解决方案。

类似的方法（此处第 7 页）：

令m[i]为以元素 结尾的任何子数组的最大总和a[i]。 m[i]那么就是max(a[i], m[i-1]+a[i])。

这是O(n).

并且您无法获得下面的任何内容O(n)，因为您必须至少访问数组的每个项目一次才能计算结果。