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