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