2

本で LIS のコードを見つけましたが、その正しさを証明することはできません。誰かがそれで私を助けることができますか？コードが行っているのは、新しい要素が最大値でない場合、セット内の新しく挿入された要素の隣にある要素を削除することだけです。それ以外の場合は、新しい要素を挿入するだけです。

    set<int> s;
    set<int>::iterator it;
    for(int i=0;i<n;i++)
    {
         s.insert(arr[i]);
             it=s.find(arr[i]);
         it++; 
         if(it!=s.end()) 
           s.erase(it);
    }
    cout<<s.size()<<endl;

n はシーケンスのサイズで、arr はシーケンスです。「厳密に」増加するシーケンスを見つける必要がない場合、次のコードが機能するとは思いません。コードを変更して、等式が許可される増加シーケンスを見つけることができますか?

編集: アルゴリズムは、入力が異なる場合にのみ機能します。

4

4 に答える 4

3

LIS にはいくつかのソリューションがあります。最も典型的なのは、動的計画法を使用した O(N^2) アルゴリズムです。ここでは、すべてのインデックス i について、「インデックス i で終わる最長の増加シーケンス」を計算します。巧妙なデータ構造またはバイナリ検索を使用して、これを O(N log N) まで高速化できます。

コードはこれをバイパスし、LIS の長さのみを計算します。入力「1 3 4 5 6 7 2」を考えると、最後のセットの内容は「1 2 4 5 6 7」になります。これは LIS ではありませんが、長さは正しいです。証明は、次のように帰納法を使用して行う必要があります。

i 番目の繰り返しの後、j 番目に小さい要素は、配列の最初の i 要素の長さ j の増加するシーケンスの最小の可能な端です。

入力「1 3 2」を検討してください。2 回目の反復の後、「1 3」を設定したので、1 は長さ 1 の増加シーケンスの可能な限り最小の終了であり、3 は長さ 2 の増加シーケンスの可能な最小の終了です
。3 回目の反復の後、「1 2」を設定しました。 2 は、長さ 2 の増加するシーケンスの可能な限り小さい終わりです。

自分で誘導ステップを実行できることを願っています:)

于 2013-09-01T14:18:16.777 に答える
2

証明は比較的簡単です: setsをソートされたリストと考えてください。ループ不変式で証明できます。アルゴリズムの各反復の後、これまでに検討した のゼロから最後の要素までのサブ配列の長さの昇順のサブシーケンスを終了するs[k]の最小要素が含まれます。これは帰納法によって証明できます。arrkarr

  • 最初の反復の後、このステートメントは true にsなります。これは、1 つの要素の自明な昇順シーケンスである 1 つの要素が含まれているためです。
  • 各反復は、次の 2 つの方法のいずれかでセットを変更できます。これまでに見つかった最大の要素が である場合に 1 ずつ拡張するか、既存の要素を以前にあった要素よりも小さい でarr[i]置き換えることができます。arr[i]

セットの拡張が発生するのは、現在の要素arr[i]を現在の LIS に追加できるためです。kのインデックスである位置 で置換が発生するarr[i]とarr[i]、長さ の昇順サブシーケンスが終了し、長さの前の「最適な」昇順サブシーケンスを終了するために使用されkた古いものより小さいか等しいために発生します。s[i]k

この不変条件があれば、全体が使い尽くされた後sの の最長の昇順サブシーケンスと同じ数の要素が含まれていることが簡単にわかります。arrarr

于 2013-09-01T15:33:48.710 に答える
-1

問題文：

  For A(n) :a0, a1,….an-1 we need to find LIS

  Find all elements in A(n) such that, ai<aj and i<j.
  For example: 10, 11, 12, 9, 8, 7, 5, 6
  LIS will be 10,11,12

これは、DP に基づく O(N^2) ソリューションです。

1 Finding SubProblems
Consider D(i): LIS of (a0 to ai) that includes ai as a part of LIS.
2 Recurrence Relation
D(i) = 1 + max(D(j) for all j<i) if ai > aj
3 Base Case
D(0) = 1;

コードのリンクを確認してください: https://innosamcodes.wordpress.com/2013/07/06/longest-increasing-subsequence/

于 2013-09-01T14:22:36.503 に答える