算法用於計算內部最大下降數？

給定一個序列x（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最好的算法？

我試圖使用動態編程，但這似乎是不可分割的......然後我有點失落......請你們建議嗎？回溯出路？

來源

2012-03-01 athos

遍歷系列，跟蹤下列值：

最大元件迄今
的最大下降到目前爲止

對於每個元素，有兩個可能的值爲新的最大下降：

它仍然是一樣的
它等於maximumElementSoFar - newElement

所以選擇一個給出更高的價值。迭代結束時的最大下降將是你的結果。這將工作在線性時間和不斷增加的空間。

來源

2012-03-01 09:41:37 interjay

thx男人，這解決了我的頭痛:) – athos 2012-03-01 11:18:40

如果我正確理解你，你有一個數組的數組，並希望找到數組中兩個相鄰元素之間的最大正差異？

由於您將不得不經過數組至少一次來計算差異，我不明白爲什麼您不能只保留一條記錄，因爲您發現的最大差異是如此遠遠（及其位置），隨着變化而更新。

如果您的問題與我所瞭解的一樣簡單，我不確定您爲什麼需要考慮動態編程。我希望我誤解了這個問題。

來源

2012-03-01 09:39:19

元素不需要是相鄰的。 – interjay 2012-03-01 09:41:58

然後，我認爲這個問題更加微不足道。 – 2012-03-01 09:44:35

解決這個問題是微不足道的，而不是微不足道的解決問題。 – interjay 2012-03-01 09:47:29

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-01 09:43:00 UmNyobe

這可以通過動態編程在O（n）中解決。 – interjay 2012-03-01 09:44:14

耶正確... – UmNyobe 2012-03-01 10:09:29

您可以將序列x（i）劃分爲子序列，其中每個子序列包含x（i）的下降子列表（例如，如果x = 5,4,1,2,1則x1 = 5,4 ，1和x2 = 2，1），然後在每個子列表中，您可以執行：first_in_sub_series - last_sub_series，然後比較您獲得的所有結果並找到最大值，這就是答案。

如果我正確理解這個問題，這應該爲您提供一個基本的線性算法來解決它。

e.g：

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，因爲我們正在談論X1是第一3項x的。

來源

2012-03-01 09:47:16 Odinn

不適用於8,5,7,4。你的算法給出3，但答案是4。 – interjay 2012-03-01 09:51:51

算法用於計算內部最大下降數？

回答

相關問題