4

The Hitchhiker's Guide to the Programming Contests に記載されているアルゴリズムを見つけました(注: この実装では、リストに重複がないことを前提としています):

set<int> st;
set<int>::iterator it;
st.clear();

for(i=0; i<n; i++) {

  st.insert(array[i]); it=st.find(array[i]);

  it++; if(it!=st.end()) st.erase(it);
}

cout<<st.size()<<endl;

O(NlogN) で最も長く増加する部分列を見つけるアルゴリズムです。いくつかのテストケースで動作させようとすると、動作するようです。しかし、私はまだその正当性ロジックを理解できませんでした。また、私にはそれほど直感的に見えません。

このアルゴリズムが正しく機能する理由について洞察を得るのを手伝ってくれる人はいますか?

4

2 に答える 2

4

ステートメント:各 i について、現在のセットの長さは、最大の増加するサブシーケンスの長さに等しくなります。

証明:帰納法を使ってみましょう:

基本ケース :自明に真。

帰納仮説: i-1 個の要素を処理し、セットの長さが LIS[i-1]、つまり最初の i-1 個の要素で可能な LIS の長さとします。

誘導ステップ:セットに要素配列 [i] を挿入すると、2 つのケースが発生します。

  1. A[i] >= set.last() : この場合、A[i] はセット内の最後の要素になるため、LIS[i] = LIS[i-1]+1 になります。

  2. A[i] < set.last() : この場合、A[i] をセットに挿入し、ソートされた順序で A[i] よりも大きい要素をノックオフします。LIS[i] = LIS[i-1] + 1(A[i] を追加) - 1 (1 つの要素を削除 > A[i])。これは本当です。よって証明された.

全体像を説明します。セットに A[i] を挿入すると、LIS[i-1] に追加されるか、0 番目の位置から i 番目の要素の位置までの要素となる独自の LIS が作成されます。

于 2014-05-02T17:03:57.570 に答える
2

動的計画法を使用して最長増加サブシーケンスを決定する方法は?

最初に私の説明を読んでください。それでもはっきりしない場合は、以下をお読みください。

アルゴリズムは、LISすべての長さの可能な限り小さい終了番号を保持します。LIS最小の数値を維持することで、最大の方法で拡張できます。これが証明ではないことはわかっていますが、直感的にわかるかもしれません。

于 2013-12-14T20:57:19.737 に答える