シリーズのアルゴリズムは内部の最大降下を計算する？

Question

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を計算するための最良のアルゴリズムは何ですか？

私はダイナミックプログラミングを使用しようとしましたが、これは分割可能ではないようです...次に少し失われています...お元気ですか？退出を後戻りしていますか？

Answer 1

直列反復処理は、以下の値を追跡する：

• 最大要素をこれまで
• 最大降下をこれまで

各要素について、2つの可能な値が存在します新しい最大降下の場合：

• 同じままです。
• これはmaximumElementSoFar - newElement

ですので、より高い値を与えるものを選んでください。反復の終了時の最大降下があなたの結果になります。これは線形時間と一定の追加空間で動作します。

Answer 2

あなたが正しく理解していれば、数字の配列があり、配列の隣り合った2つの要素の間に最大の正の違いがありますか？

あなたは少なくとも一度アレイを通過しなければならないので、違いを計算するためには、見つかった最大の違いを記録しておくことができません遠くに（そしてその場所の）、そのように更新する。

私が理解しているほど問題が簡単なのであれば、なぜ動的プログラミングについて考える必要があるのか​​分かりません。私はその質問を誤解していると思います。

Answer 3

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

は、あなただけはO（n^2）であるすべての値についてのx（I）-x（j）を、計算し、その後、最大を取得する必要があります。動的プログラミングの必要はありません。

Answer 4

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 

DMAX = 4及びIM = 1、JM = 3我々は、xの最初の3つの項目であるX1について話しているからです。