arrays - 最快的算法顺序移动通过数组

Question

假设您有一个包含正整数和负整数的数组。如果你站在第 i 个位置，你可以移动到第 i+1 个或第 i+2 个位置。任务是找到路径，你应该如何移动，以获得所有收集值的最大总和。解决这个问题的最快算法是什么？谢谢。

例子：

0 1 8 -7 -10 -30 -1 -4 -5 0

0 1 8 -10 -1 -4 0 最大总和 -6

Answer 1

这是动态规划的经典例子。

对于每个位置，您将计算到达该位置可达到的最大总和。位置i可以从位置i-1或i-2到达，所以：

maxsum[i] = max(maxsum[i-2], maxsum[i-1]) + val[i]

您只需要使用起始值遍历数组：maxsum[<0] = 0.

复杂度：O(n)。

0 1 8 -7 -10 -30 -1 -4 -5 0

0 1 9 2  -1  -28 -2 -6 -7 -6