0

系列 x(i) (i は 1 から N) が与えられた場合、N = 10,000 としましょう。

for any i < j,
D(i,j) = x(i) - x(j), if x(i) > x (j); or,
       = 0, if x(i) <= x(j).

定義

Dmax(im, jm) := max D(i,j), for all 1 <= i < j <=N.

Dmax、im、および jm を計算するための最適なアルゴリズムは何ですか?

動的計画法を使用しようとしましたが、これは分割できないようです...それから私は少し迷っています...提案してもらえますか? バックトラックは逃げ道ですか？

4

4 に答える 4

2

次の値を追跡しながら、系列を反復処理します。

  • 今までの最大要素
  • 今までの最大降下

各要素について、新しい最大降下には 2 つの可能な値があります。

  • それは同じままです
  • 等しいmaximumElementSoFar - newElement

したがって、より高い値を与えるものを選択します。反復終了時の最大降下が結果になります。これは、線形時間と一定の追加スペースで機能します。

于 2012-03-01T09:41:37.503 に答える
0

シリーズx（i）をサブシリーズに分割できます。各サブシリーズにはx（i）のサブリストが含まれ、降順です（たとえば、x = 5、4、1、2、1の場合、x1 = 5、4、1、x2 = 2、1）次に、各サブリストで次の操作を実行できます。first_in_sub_series--last_sub_series次に、取得したすべての結果を比較して最大値を見つけます。これが答えです。

私が問題を正しく理解した場合、これはそれを解決するための基本的な線形アルゴリズムを提供するはずです。

例えば：

x = 5, 4, 1, 2, 1 then x1 = 5, 4, 1 and x2 = 2, 1
rx1 = 4
rx2 = 1

xの最初の3つの項目であるx1について話しているので、dmax=4およびim=1およびjm=3です。

于 2012-03-01T09:47:16.887 に答える
0

あなたが正しく理解している場合、数値の配列があり、配列の2つの隣接する要素間の最大の正の差を見つけたいですか?

違いを計算するには、配列を少なくとも 1 回調べる必要があるため、これまでに見つかった最大の違い (およびその場所)、その変更に応じて更新します。

問題が私が理解しているほど単純である場合、なぜ動的計画法について考える必要があるのか​​ わかりません。私は質問を誤解したと思います。

于 2012-03-01T09:39:19.113 に答える
0

Dmax(im, jm) := max D(i,j) = max(x(i) -x(j),0) = max(max(x(i) -x(j)),0)

x(i) -x(j) をすべての値 O(n^2) に対して計算し、最大値を取得するだけです。動的計画法は必要ありません。

于 2012-03-01T09:43:00.340 に答える