是否有針對這些問題的特定算法？

我碰到一對夫婦，其中有幾個項目在集合Ë_{類似的問題來到我} = {白_我，H _我}爲i=0..n，你必須找到最長的系列，從而瓦特_米>瓦特_{米+ 1}和ħ_米>ħ_{米+ 1}用於m每個succesive值。聽起來很熟悉嗎？任何人都可以指出可能已經處理類似問題的特定算法嗎？是否有針對這些問題的特定算法？

來源

2011-12-14 user1098204

[最長增長子序列]（http://en.wikipedia.org/wiki/Longest_increasing_subsequence）與各種部分訂單。 – Per 2011-12-14 16:22:58

@Per這不是最長的公共子序列，因爲e1 =（3,4），e2 =（2,5）沒有關係（不是<,>，=），所以你不能使用二分搜索。或者其他任何已知的基於比較的方法。 – 2011-12-14 18:03:38

這樣做的一種方法是構建一個有向無環圖，該有向無環圖具有每個ei的節點以及從ei到ej（在上面說明的意義上）的邊。然後find the longest path in this DAG。

來源

2011-12-14 16:58:10

+1不錯的答案。 – 2011-12-14 18:00:36

您正在尋找時間最長的子序列，因此patience sorting可能是最佳選擇。

當您執行此操作時，您需要編寫自己的比較器方法，該方法說e_i < e_j當且僅當w_i < w_j和h_i < h_j。您有部分訂單而不是全部訂單的事實不會改變算法。

來源

2011-12-14 18:50:23 PengOne

是否有針對這些問題的特定算法？

回答

相關問題