配列順序を作るために最小限のサブセットを削除するアルゴリズム

Question

私は、おそらくソートされたシーケンス内の "異常値"を検出したいという状況があります。順序を破る要素は疑わしいとみなされます。

は、例えばシーケンス1, 2, 3, 4, 7, 5, 6, 8, 9がソートされていない、しかし、あなたが削除した場合、あなたが5と6を削除し、それを持ったときにちょうどまた7を（削除以上であれば7あなたはソート順序1, 2, 3, 4, 5, 6, 8, 9を取得し、これもまた真であります並べ替えられたシーケンスは、任意の要素を削除して、並べ替えられたシーケンスを持つことができます）。

これを行うための効率的なアルゴリズムはありますか？同じように良い解決策を見つけるアルゴリズムはありますか？

たとえば、1, 3, 2, 4というシーケンスがある場合は、後になります。 3を削除して並べ替えられたシーケンスを取得することもできますが、ちょうど2を削除してソートされたシーケンスを取得することもできます（どちらのソリューションも1つの要素しか削除されないので同等です）。

Answer 1

これは、O(N²)で動的プログラムまたはメモ再帰によって行うことができます。 （インデックス

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)) 

} 

あなたはコーナーケースを処理する必要があります。foo(n,m)がソートされたサブセットの最大の長さを表している場合、最後の要素のインデックスはmその後、再帰関数がある添加したときのインデックスnから（私は、サブシーケンスが正しい言葉だと思います）配列の長さに等しい）とmemoizationを追加して動作させるが、私はあなたにそれを残す。また、wikiページではさらに高速な実装が可能です。

Answer 2

この問題は、最も長くなるサブシーケンスを見つけることと同様です。 nlogためhttp://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/

とhttp://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/（n）を実装：O（N^2）実施のため

文献。