私が理解できないことが1つあります：
X[M[i]] が非減少シーケンスなのはなぜですか?
質問する
52270 次
8 に答える
86
まず、n^2 アルゴリズムを見てみましょう。
dp[0] = 1;
for( int i = 1; i < len; i++ ) {
dp[i] = 1;
for( int j = 0; j < i; j++ ) {
if( array[i] > array[j] ) {
if( dp[i] < dp[j]+1 ) {
dp[i] = dp[j]+1;
}
}
}
}
改善は 2 番目のループで行われるようになりました。基本的には、二分探索を使用して速度を改善できます。配列 dp[] に加えて、別の配列 c[] を用意しましょう。c は非常に特殊です。c[i] は、長さが i である最長増加シーケンスの最後の要素の最小値を意味します。
sz = 1;
c[1] = array[0]; /*at this point, the minimum value of the last element of the size 1 increasing sequence must be array[0]*/
dp[0] = 1;
for( int i = 1; i < len; i++ ) {
if( array[i] < c[1] ) {
c[1] = array[i]; /*you have to update the minimum value right now*/
dp[i] = 1;
}
else if( array[i] > c[sz] ) {
c[sz+1] = array[i];
dp[i] = sz+1;
sz++;
}
else {
int k = binary_search( c, sz, array[i] ); /*you want to find k so that c[k-1]<array[i]<c[k]*/
c[k] = array[i];
dp[i] = k;
}
}
于 2011-09-30T18:13:59.620 に答える
25
これは、 The Hitchhiker's Guide to the Programming Contestsの O(n*lg(n)) ソリューションです(注: この実装では、リストに重複がないことを前提としています)。
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;
重複を考慮するには、たとえば、番号がすでにセットに含まれているかどうかを確認できます。そうである場合は、その番号を無視し、そうでない場合は、以前と同じ方法を使用して続行します。または、操作の順序を逆にすることもできます。最初に削除し、次に挿入します。以下のコードは、この動作を実装しています。
set<int> st;
set<int>::iterator it;
st.clear();
for(int i=0; i<n; i++) {
it = st.lower_bound(a[i]);
if (it != st.end()) st.erase(it);
st.insert(a[i]);
}
cout<<st.size()<<endl;
2 番目のアルゴリズムを拡張して、元の配列内の LIS の前の要素の位置を含む親配列を維持することにより、最長増加部分列 (LIS) 自体を見つけることができます。
typedef pair<int, int> IndexValue;
struct IndexValueCompare{
inline bool operator() (const IndexValue &one, const IndexValue &another){
return one.second < another.second;
}
};
vector<int> LIS(const vector<int> &sequence){
vector<int> parent(sequence.size());
set<IndexValue, IndexValueCompare> s;
for(int i = 0; i < sequence.size(); ++i){
IndexValue iv(i, sequence[i]);
if(i == 0){
s.insert(iv);
continue;
}
auto index = s.lower_bound(iv);
if(index != s.end()){
if(sequence[i] < sequence[index->first]){
if(index != s.begin()) {
parent[i] = (--index)->first;
index++;
}
s.erase(index);
}
} else{
parent[i] = s.rbegin()->first;
}
s.insert(iv);
}
vector<int> result(s.size());
int index = s.rbegin()->first;
for(auto iter = s.rbegin(); iter != s.rend(); index = parent[index], ++iter){
result[distance(iter, s.rend()) - 1] = sequence[index];
}
return result;
}
于 2012-09-29T23:03:29.927 に答える
13
増加するシーケンスのリストを維持する必要があります。
一般に、さまざまな長さのアクティブなリストのセットがあります。これらのリストに要素 A[i] を追加しています。リストの長さの降順で (終了要素の) リストをスキャンします。すべてのリストの end 要素を検証して、end 要素が A[i] (floor 値) より小さいリストを見つけます。
次の条件によって決定される戦略は、
1. A[i] がアクティブ リストのすべてのエンド候補の中で最小の場合、長さ 1 の新しいアクティブ リストを開始します。
2. A[i] がアクティブ リストのすべてのエンド候補の中で最大の場合リストの場合、最大のアクティブ リストを複製し、A[i] だけ拡張します。
3. A[i] が中間にある場合、A[i] より小さい最大の終了要素を持つリストが見つかります。このリストを A[i] で複製して拡張します。この変更されたリストと同じ長さの他のすべてのリストを破棄します。
アクティブ リストの作成中は常に、次の条件が維持されることに注意してください。
「小さいリストの最後の要素は、大きいリストの最後の要素よりも小さい」。
wiki から例を挙げてみましょう:
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.
A[0] = 0. ケース 1. アクティブなリストがない場合は作成します。
0
.------------------------------------------------ -----------------------------
A[1] = 8. ケース 2. 複製して拡張します。
0.0、8 .------------------------------------------------
_
---------------------------------
A[2] = 4. ケース 3. 複製、拡張、破棄。
0.0、4.0、8
.
破棄
--------------------------------------- --------------------------------------
A[3] = 12. ケース 2. クローンと拡張する。
0.0、4.0、4、12
. --------------------------------------
_
---------------------------------------
A[4] = 2. ケース 3. クローン、拡張して破棄します。
0.0、2
.
0、4。破棄。
0、4、12
。------------------------------------------------ ---------------------------------
A[5] = 10. ケース 3. 複製、拡張、破棄。
0.
0、2
.
0、2、10. 0、4、12. 破棄。
-------------------------------------------------- ---------------------------
A[6] = 6. ケース 3. 複製、拡張、破棄。
0.
0、2 .
0、2、6
. 0、2、10. 破棄。
-------------------------------------------------- ---------------------------
A[7] = 14. ケース 2. 複製して拡張します。
0.
0, 2.
0, 2, 6.
0, 2, 6, 14.
------------------------------ -----------------------------------------------
A[8] = 1. ケース 3. 複製、拡張、破棄。
0.0、1.0、2
.
破棄。
0, 2, 6.
0, 2, 6, 14.
---------------------------------- -----------------------------------------
A[9] = 9. ケース 3 . クローン、拡張、破棄。
0.
0、1 .
0、2、6 .
0、2、6、9
. 0、2、6、14. 破棄。
-------------------------------------------------- ---------------------------
A[10] = 5. ケース 3. 複製、拡張、破棄。
0.
0、1 . 0、1、5.
0、2、6
. 破棄。
0、2、6、9 。
------------------------------------------ -----------------------------------
A[11] = 13. ケース 2. 複製して拡張します。
0.
0, 1.
0, 1, 5.
0, 2, 6, 9.
0, 2, 6, 9, 13.
---------------------- -------------------------------------------------- -----
A[12] = 3. ケース 3. 複製、拡張、破棄。
0.
0、1 .
0、1、3
. 0、1、5. 破棄。
0, 2, 6, 9.
0, 2, 6, 9, 13.
-------------------------------- ---------------------------------------------
A[13] = 11. ケース 3. クローン、拡張、破棄。
0.
0、1 .
0、1、3 .
0、2、6、9 .
0、2、6、9、11
. 0、2、6、9、13. 破棄。
-------------------------------------------------- ---------------------------
A[14] = 7. ケース 3. 複製、拡張、破棄。
0.
0, 1.
0, 1, 3.
0, 1, 3, 7. 0, 2, 6, 9. 破棄。
0、2、6、9、11 。
------------------------------ ------------------------------------
A[15] = 15. ケース 2. 複製して拡張します。
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9, 11.
0, 2, 6, 9, 11, 15. <-- LIS リスト
また、「小さなリストの終了要素は、大きなリストの終了要素よりも小さい」という条件を維持していることを確認してください。
このアルゴリズムは、Patience Sorting と呼ばれます。
http://en.wikipedia.org/wiki/Patience_sorting
それで、カードのデッキからスーツを選びます。シャッフルされたスートからカードの最も長く増加するサブ シーケンスを見つけます。アプローチを忘れることはありません。
複雑度 : O(NlogN)
ソース: http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
于 2013-07-15T17:53:24.543 に答える
0
アルゴリズムの背後にある基本的な考え方は、可能な限り最小の要素で終わる特定の長さの LIS のリストを保持することです。そのようなシーケンスの構築
- 既知の最後の要素シーケンスで直前の要素を検索します (その長さを言いましょう
k) - 現在の要素をこのシーケンスに追加して、
k+1長さの新しいより良いソリューションを構築してみてください
最初のステップでは X[i] よりも小さい値を検索するため、新しいソリューション ( の場合k+1) は、最後の要素がより短いシーケンスよりも大きくなります。
それが役立つことを願っています。
于 2011-05-25T19:51:35.083 に答える