刪除最小子集以生成序列順序的算法

Question

我有一種情況，我想要在所謂的排序序列中檢測「異常值」。破壞訂單的元素被認爲是可疑的。

例如序列1, 2, 3, 4, 7, 5, 6, 8, 9不排序，但如果去掉7你得到一個排序序列1, 2, 3, 4, 5, 6, 8, 9，這一點，如果你刪除5和6，但比剛取出7（也有當更多的也是如此一個排序的序列，你可以刪除任意元素，並仍然有一個排序序列）。

有沒有一個有效的算法來做到這一點？有沒有一種算法可以找到所有同樣好的解決方案？

後面是例如，如果你有序列1, 3, 2, 4。您可以刪除3以獲得排序序列，但您也可以刪除2以獲得排序序列（兩種解決方案同樣好，因爲它們只刪除一個元素）。

Answer 1

這可以通過動態程序或記憶遞歸在O(N²)中完成。如果foo(n,m)代表排序子集的最大長度（我覺得子序列是正確的單詞）從指數n當最後一個元素的索引加入爲m然後遞歸函數是：

int foo(int n,int m) { 
    int res = 0; 
    // you can add this number in the current sequence 
    //if its greater than the previous element in the sequence 
    // seq is array containing the numbers 
    if (seq[n] >= seq[m]) { 
     //1 because we added this element 
     // second argument is n because n is now the last element added 
     res = 1 + foo (n+1, n); 
    } 
    // you can always skip the current element 
    // in that case m remains same 
    res = max (res, foo(n+1, m)) 

} 

您將需要處理的情況（指數等於數組長度）並添加備忘錄以使其工作，但我會將其留給您。此外，wiki頁面的實現速度更快。

Answer 2

此問題類似於查找時間最長的子序列。

價爲爲O（n^2）執行：http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/

和http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/爲n日誌（n）的實施方式。