我有一種情況,我想要在所謂的排序序列中檢測「異常值」。破壞訂單的元素被認爲是可疑的。刪除最小子集以生成序列順序的算法
例如序列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
以獲得排序序列(兩種解決方案同樣好,因爲它們只刪除一個元素)。
https://en.wikipedia.org/wiki/Longest_increasing_subsequence – x1Mike7x