1

N 個の数値 (正と負) と T = 選択できる数値の数が与えられた場合、間隔の最大合計をどのように計算できますか? 間隔の最初の数値は 0 と見なされます。

例: N=5 T=4 and {3 9 1 1 7} (3, 9) と (1, 7) の最大合計は 16 です。3 と 1 は間隔の最初の数値であるため、0 と見なされることに注意してください。これに対する解決策を思いつきましたが、負の数を追加するとめちゃくちゃになります。N=4 T=3 と {-2 1 -3 -4} の解は 1 (-2, 1) と (-3 -3) です (負の数を扱う場合、同じ負の数によって形成される間隔を考慮することができます数 (-3 -3) = 0)。何か案は？

*後で編集: 私のコードの何が問題なのですか? http://pastebin.com/QTTTrvUz

4

1 に答える 1

1

動的計画法はあなたの友達です:

数を選択できる場合、最初の数S[i][j]のみを考慮して取得できる最大合計を とします。ij

次に、次のいずれかを行います。

  1. S[i][j] = S[i - 1][j]i、セグメントにない場合。
  2. S[i][j] = S[i - k][j - k] + value_of_segment(i - k + 1, i)i、長さのセグメント内にある場合k。

みましょうS[i][j] = max((1), (2))。

value_of_segmentで事前計算できますO(n)。

S[i][j]で計算できますO(N * T^2)。

于 2013-03-20T22:14:56.780 に答える